Structure and properties of large intersecting families

Andrey Kupavskii111Moscow Institute of Physics and Technology, Ecole Polytechnique Fédérale de Lausanne; Email: kupavskii@yandex.ru   Research supported by the grant RNF 16-11-10014.
Abstract

We say that a family of k𝑘k-subsets of an n𝑛n-element set is intersecting, if any two of its sets intersect. In this paper we study different extremal properties of intersecting families, as well as the structure of large intersecting families. We also give some results on k𝑘k-uniform families without s𝑠s pairwise disjoint sets, related to Erdős Matching Conjecture.

We prove a conclusive version of Frankl’s theorem on intersecting families with bounded maximal degree. This theorem, along with its generalizations to cross-intersecting families, implies many results on the topic, obtained by Frankl, Frankl and Tokushige, Kupavskii and Zakharov and others.

We study the structure of large intersecting families, obtaining some general structural theorems which generalize the results of Han and Kohayakawa, as well as Kostochka and Mubayi.

We give degree and subset degree version of the Erdős–Ko–Rado and the Hilton–Milner theorems, extending the results of Huang and Zhao, and Frankl, Han, Huang and Zhao. We also extend the range in which the degree version of the Erdős Matching conjecture holds.

1 Introduction

Let [n]:={1,,n}assigndelimited-[]𝑛1𝑛[n]:=\{1,\ldots,n\} and denote 2[n]superscript2delimited-[]𝑛2^{[n]} the power set of [n]delimited-[]𝑛[n]. For integers ab𝑎𝑏a\leq b we put [a,b]:={a,a+1,,b}assign𝑎𝑏𝑎𝑎1𝑏[a,b]:=\{a,a+1,\ldots,b\} and for integers 0kn0𝑘𝑛0\leq k\leq n we denote ([n]k)binomialdelimited-[]𝑛𝑘{[n]\choose k} the collection of all k𝑘k-element subsets (k𝑘k-sets) of [n]delimited-[]𝑛[n]. Any collection of sets 2[n]superscript2delimited-[]𝑛\mathcal{F}\subset 2^{[n]} we call a family. We call a family intersecting, if any two sets from it intersect. A “trivial” example of such family is all sets containing a fixed element. We call a family non-trivial, if not all of its sets contain the same element.

One of the oldest and most famous results in extremal combinatorics is the Erdős–Ko–Rado theorem:

Theorem 1 ([3]).

Let n2k>0𝑛2𝑘0n\geq 2k>0 and consider an intersecting family ([n]k)binomialdelimited-[]𝑛𝑘\mathcal{F}\subset{[n]\choose k}. Then ||(n1k1)binomial𝑛1𝑘1|\mathcal{F}|\leq{n-1\choose k-1}. Moreover, for n>2k𝑛2𝑘n>2k the only families attaining this bound are the families of all k𝑘k-sets containing a given element.

Answering a question of Erdős, Ko, and Rado, Hilton and Milner [16] found the largest non-trivial intersecting family of k𝑘k-sets. Up to permutation of the ground sets, it is the family consisting of the set [2,k+1]2𝑘1[2,k+1] and all sets that contain 111 and intersect [2,k+1]2𝑘1[2,k+1]. Such family has size (n1k1)(nk1k1)+1binomial𝑛1𝑘1binomial𝑛𝑘1𝑘11{n-1\choose k-1}-{n-k-1\choose k-1}+1, which is much smaller than (n1k1)binomial𝑛1𝑘1{n-1\choose k-1} provided n𝑛n is large as compared to k𝑘k.

This paper is mostly concerned with the properties of large intersecting families. It is separated in several relatively independent parts covering different topics. Below we give the summary of the topics covered and the structure of the paper.

  1. Section 3:

    In this section we give a conclusive version of the Frankl’s degree theorem (see Theorems 23 in the next section). The main result gives the precise dependence of size of the family on (lower bound on) the number of sets not containing the most popular element. The result then is extended to cover the equality case, as well as the weighted case and the case of cross-intersecting families. It, in particular, strengthens the results of [5], [12], [24].

  2. Section 4:

    In this section we address the question, what is the structure of large intersecting families. Unlike in Section 3, where, due to the Kruskal-Katona theorem, we have to deal with lexicographical families only (for definitions and necessary results, see the next section), in this section we work with general families. We prove several results, which, in particular, cover a large part of results of [14], [20], and extend them much farther. One important advantage, as compared to the results of [20], is that the results do not require n𝑛n to be large w.r.t. k𝑘k.

  3. Section 5:

    In this section we obtain degree and subset degree versions of the Erdős-Ko-Rado theorem and the Hilton-Milner theorem. This answers some of the questions posed by Huang and extends the results of [17], [13], [8].

  4. Section 6:

    In this section we obtain an upper bound on the minimum degree of a family ([n]k)binomialdelimited-[]𝑛𝑘\mathcal{F}\subset{[n]\choose k}, which does not contain s𝑠s pairwise disjoint sets. The results extends the analogous result of [17] for large k𝑘k. The problem in question may be seen as a degree vesion of the Erdős Matching Conjecture.

Some of the results in Section 4 depend on the results from Section 5, while Section 6 is relatively independent from the previous two sections. Section 6 is completely independent.

In the next section we give some of the definitions and results crucial for the paper. In Section 7 we give some concluding remarks and state several open problems.

2 Preliminaries

The degree δ(i)𝛿𝑖\delta(i) of an element i𝑖i is the number of sets from the family containing it. For a family \mathcal{F} the diversity γ()𝛾\gamma(\mathcal{F}) is the quantity ||Δ()Δ|\mathcal{F}|-\Delta(\mathcal{F}), where Δ()Δ\Delta(\mathcal{F}) is the maximal degree of an element in \mathcal{F}. Below we discuss the connection between the diversity and the size of an intersecting family.

We will need the following result due to Kupavskii and Zakharov [24]. It is a slightly stronger version of Frankl’s result [5]:

Theorem 2 ([24]).

Let n>2k>0𝑛2𝑘0n>2k>0 and ([n]k)binomialdelimited-[]𝑛𝑘\mathcal{F}\subset{[n]\choose k} be an intersecting family. Then, if γ()(nu1nk1)𝛾binomial𝑛𝑢1𝑛𝑘1\gamma(\mathcal{F})\geq{n-u-1\choose n-k-1} for some real 3uk3𝑢𝑘3\leq u\leq k, then

||(n1k1)+(nu1nk1)(nu1k1).binomial𝑛1𝑘1binomial𝑛𝑢1𝑛𝑘1binomial𝑛𝑢1𝑘1|\mathcal{F}|\leq{n-1\choose k-1}+{n-u-1\choose n-k-1}-{n-u-1\choose k-1}. (1)

The bound from Theorem 2 is sharp for integer u𝑢u, as witnessed by the example

u:={A([n]k):[2,u]A}{A([n]k):1A,[2,u]A}.assignsubscript𝑢conditional-set𝐴binomialdelimited-[]𝑛𝑘2𝑢𝐴conditional-set𝐴binomialdelimited-[]𝑛𝑘formulae-sequence1𝐴2𝑢𝐴\mathcal{H}_{u}:=\{A\in{[n]\choose k}:[2,u]\subset A\}\cup\{A\in{[n]\choose k}:1\in A,[2,u]\cap A\neq\emptyset\}.

We note that the case u=k𝑢𝑘u=k of Theorem 2 is precisely the Hilton-Milner theorem.

To allow the reader to compare Theorem 2 and the original Frankl’s theorem, let us state it here.

Theorem 3 ([5]).

Let n>2k>0𝑛2𝑘0n>2k>0 and ([n]k)binomialdelimited-[]𝑛𝑘\mathcal{F}\subset{[n]\choose k} be an intersecting family. Then, if Δ()(n1k1)(nu1k1)Δbinomial𝑛1𝑘1binomial𝑛𝑢1𝑘1\Delta(\mathcal{F})\leq{n-1\choose k-1}-{n-u-1\choose k-1} for some integer 3uk3𝑢𝑘3\leq u\leq k, then

||(n1k1)+(nu1nk1)(nu1k1).binomial𝑛1𝑘1binomial𝑛𝑢1𝑛𝑘1binomial𝑛𝑢1𝑘1|\mathcal{F}|\leq{n-1\choose k-1}+{n-u-1\choose n-k-1}-{n-u-1\choose k-1}.

We note that Theorem 3 is immediately implied by Theorem 2, while in the other direction it is not true, even for the integer values of u𝑢u.

One of the key ingredients in the proofs of several theorems is the Kruskal-Katona theorem. Below we state it in terms of lexicographical orderings. Let us first give some definitions. A lexicographical order (lex) << on the sets from ([n]k)binomialdelimited-[]𝑛𝑘{[n]\choose k} is an order, in which A<B𝐴𝐵A<B iff the minimal element of AB𝐴𝐵A\setminus B is smaller than the minimal element of BA𝐵𝐴B\setminus A. For 0m(nk)0𝑚binomial𝑛𝑘0\leq m\leq{n\choose k} let (m,k)𝑚𝑘\mathcal{L}(m,k) be the collection of m𝑚m largest sets with respect to lex.

We say that two families 𝒜,𝒜\mathcal{A},\mathcal{B} are cross-intersecting, if for any A𝒜,Bformulae-sequence𝐴𝒜𝐵A\in\mathcal{A},B\in\mathcal{B} we have AB𝐴𝐵A\cap B\neq\emptyset.

Theorem 4 ([21],[19]).

Suppose that 𝒜([n]a),([n]b)formulae-sequence𝒜binomialdelimited-[]𝑛𝑎binomialdelimited-[]𝑛𝑏\mathcal{A}\subset{[n]\choose a},\mathcal{B}\subset{[n]\choose b} are cross-intersecting. Then the families (|𝒜|,a),(||,b)𝒜𝑎𝑏\mathcal{L}(|\mathcal{A}|,a),\mathcal{L}(|\mathcal{B}|,b) are also cross-intersecting.

3 The complete diversity version of Frankl’s theorem

In this section we study in detail the relationship between the diversity of an intersecting family and its size. First, note that, if the value of diversity is given precisely, then it is very easy to determine the largest intersecting family with such diversity using Theorem 4. Studying the size of an intersecting family with given upper bounds on diversity is not interesting: in general, the smaller the diversity is, the larger families with such diversity exist.

In this section we obtain a strengthened version of Theorem 2, which will tell exactly, how large an intersecting family may be, given a lower bound on its diversity. We give all “extremal” values of diversity and the sizes of the corresponding families.

The difficulty to obtain such a version of Theorem 2 is that, while Theorem 4 gives a very strong and clear characterisation of families with fixed diversity, the size of the family is not monotone w.r.t. diversity (the size of the largest family with a given diversity does not necessarily decrease when diversity increases, although it is true in most cases), and an extra effort is needed to find the right point of view.

We will give two versions of the main theorem of this section. First, we give a “numerical” version with explicit sharp bounds on the size of an intersecting family. It may be more practical to apply in some cases, but it is difficult to grasp, what is hidden behind the binomial coefficients in the formulation. Thus, later in the section (and as an intermediate step of the proof), we will give a “conceptual” version of our main theorem. We note that the proof that we present is completely computation-free. In the later parts of this section we present strengthenings and generalisations of our main result. We will settle the equality case in Theorems 67, as well as consider the weighted case and a generalization to the case of general cross-intersecting families.

We note that the main results of the section are meaningful for any k3𝑘3k\geq 3.

The following representation of natural numbers is important for the (classic form of) the Kruskal-Katona theorem. Given positive integers γ𝛾\gamma and k𝑘k, one can always write down γ𝛾\gamma uniquely in the k𝑘k-cascade form:

γ=(akk)+(ak1k1)++(ass),ak>ak1>>as1.formulae-sequence𝛾binomialsubscript𝑎𝑘𝑘binomialsubscript𝑎𝑘1𝑘1binomialsubscript𝑎𝑠𝑠subscript𝑎𝑘subscript𝑎𝑘1subscript𝑎𝑠1\gamma={a_{k}\choose k}+{a_{k-1}\choose k-1}+\ldots+{a_{s}\choose s},\ \ a_{k}>a_{k-1}>\ldots>a_{s}\geq 1.

For the sake of comparison, let us state the classical version of the Kruskal-Katona theorem (equivalent to Theorem 4).

Theorem 5 ([21],[19]).

Let ([n]k)binomialdelimited-[]𝑛𝑘\mathcal{F}\subset{[n]\choose k} and put

():={F([n]k1):FF for some F}.assignconditional-setsuperscript𝐹binomialdelimited-[]𝑛𝑘1superscript𝐹𝐹 for some 𝐹\partial(\mathcal{F}):=\big{\{}F^{\prime}\in{[n]\choose k-1}:F^{\prime}\subset F\text{ for some }F\in\mathcal{F}\big{\}}.

If ||=(akk)++(ass)binomialsubscript𝑎𝑘𝑘binomialsubscript𝑎𝑠𝑠|\mathcal{F}|={a_{k}\choose k}+\ldots+{a_{s}\choose s}, then

|()|(akk1)+(ak1k1)++(ass1).binomialsubscript𝑎𝑘𝑘1binomialsubscript𝑎𝑘1𝑘1binomialsubscript𝑎𝑠𝑠1|\partial(\mathcal{F})|\geq{a_{k}\choose k-1}+{a_{k-1}\choose k-1}+\ldots+{a_{s}\choose s-1}.

To state our theorem, we need to represent the diversity of an intersecting family in a cascade form. Given a number γ𝛾\gamma, let us write it in the (nk1)𝑛𝑘1(n-k-1)-cascade form in the following particular way:

γ=(nb1nk1)+(nb2nk2)++(nbsbns1),𝛾binomial𝑛subscript𝑏1𝑛𝑘1binomial𝑛subscript𝑏2𝑛𝑘2binomial𝑛subscript𝑏subscript𝑠𝑏𝑛𝑠1\gamma={n-b_{1}\choose n-k-1}+{n-b_{2}\choose n-k-2}+\ldots+{n-b_{s_{b}}\choose n-s-1},

where 1b1<b2<<bsb.1subscript𝑏1subscript𝑏2subscript𝑏subscript𝑠𝑏1\leq b_{1}<b_{2}<\ldots<b_{s_{b}}. Define Tγ:={b1,,bsb}assignsubscript𝑇𝛾subscript𝑏1subscript𝑏subscript𝑠𝑏T_{\gamma}:=\{b_{1},\ldots,b_{s_{b}}\} and put Sγ:={bsb}([2,bsb]Tγ)assignsubscript𝑆𝛾subscript𝑏subscript𝑠𝑏2subscript𝑏subscript𝑠𝑏subscript𝑇𝛾S_{\gamma}:=\{b_{s_{b}}\}\cup([2,b_{s_{b}}]\setminus T_{\gamma}). Note that SγTγ=[2,bsb]subscript𝑆𝛾subscript𝑇𝛾2subscript𝑏subscript𝑠𝑏S_{\gamma}\cup T_{\gamma}=[2,b_{s_{b}}] and SγTγ={bsb}subscript𝑆𝛾subscript𝑇𝛾subscript𝑏subscript𝑠𝑏S_{\gamma}\cap T_{\gamma}=\{b_{s_{b}}\}. We assume that Sγ={a1,,asa}subscript𝑆𝛾subscript𝑎1subscript𝑎subscript𝑠𝑎S_{\gamma}=\{a_{1},\ldots,a_{s_{a}}\}, where 2a1<<asa=bsb2subscript𝑎1subscript𝑎subscript𝑠𝑎subscript𝑏subscript𝑠𝑏2\leq a_{1}<\ldots<a_{s_{a}}=b_{s_{b}}.

We call a number γ𝛾\gamma resistant, if the following holds:

  1. 1.

    sa=|Sγ|ksubscript𝑠𝑎subscript𝑆𝛾𝑘s_{a}=|S_{\gamma}|\leq k, sb=|Tγ|k1subscript𝑠𝑏subscript𝑇𝛾𝑘1s_{b}=|T_{\gamma}|\leq k-1;

  2. 2.

    bi>2i+2subscript𝑏𝑖2𝑖2b_{i}>2i+2 for each i[sb]𝑖delimited-[]subscript𝑠𝑏i\in[s_{b}];

  3. 3.

    For convenience, we assume that (n4k3)binomial𝑛4𝑘3{n-4\choose k-3} is a resistant number.

Thus, in particular, any integer γ>(n4k3)𝛾binomial𝑛4𝑘3\gamma>{n-4\choose k-3} will have (n4k3)binomial𝑛4𝑘3{n-4\choose k-3} as one of the members in the (nk1)𝑛𝑘1(n-k-1)-cascade form, so such γ𝛾\gamma is not resistant.

Let 1=γ1<γ2<<γm=(n4k3)1subscript𝛾1subscript𝛾2subscript𝛾𝑚binomial𝑛4𝑘31=\gamma_{1}<\gamma_{2}<\ldots<\gamma_{m}={n-4\choose k-3} be all the resistant numbers. Put γ0=0subscript𝛾00\gamma_{0}=0 for convenience.

Theorem 6.

Let n>2k6𝑛2𝑘6n>2k\geq 6. Consider an intersecting family ([n]k)binomialdelimited-[]𝑛𝑘\mathcal{F}\subset{[n]\choose k}. Suppose that γl1<γ()γlsubscript𝛾𝑙1𝛾subscript𝛾𝑙\gamma_{l-1}<\gamma(\mathcal{F})\leq\gamma_{l} for l[m]𝑙delimited-[]𝑚l\in[m] and that the representation of γlsubscript𝛾𝑙\gamma_{l} in the (nk1)𝑛𝑘1(n-k-1)-cascade form is

γl=(nb1nk1)+(nb2nk2)++(nbsbns1),subscript𝛾𝑙binomial𝑛subscript𝑏1𝑛𝑘1binomial𝑛subscript𝑏2𝑛𝑘2binomial𝑛subscript𝑏subscript𝑠𝑏𝑛𝑠1\gamma_{l}={n-b_{1}\choose n-k-1}+{n-b_{2}\choose n-k-2}+\ldots+{n-b_{s_{b}}\choose n-s-1},

then

||(na1nk)+(na2nk1)++(nasansa)+γl,binomial𝑛subscript𝑎1𝑛𝑘binomial𝑛subscript𝑎2𝑛𝑘1binomial𝑛subscript𝑎subscript𝑠𝑎𝑛subscript𝑠𝑎subscript𝛾𝑙|\mathcal{F}|\leq{n-a_{1}\choose n-k}+{n-a_{2}\choose n-k-1}+\ldots+{n-a_{s_{a}}\choose n-s_{a}}+\gamma_{l}, (2)

where {b1,,bsb}=Tγsubscript𝑏1subscript𝑏subscript𝑠𝑏subscript𝑇𝛾\{b_{1},\ldots,b_{s_{b}}\}=T_{\gamma} and {a1,,asa}=Sγsubscript𝑎1subscript𝑎subscript𝑠𝑎subscript𝑆𝛾\{a_{1},\ldots,a_{s_{a}}\}=S_{\gamma}.

The expression in the right hand side of (2) strictly decreases as l𝑙l increases.

Moreover, the presented bound is sharp: for each l=1,,m𝑙1𝑚l=1,\ldots,m there exists an intersecting family with diversity γlsubscript𝛾𝑙\gamma_{l} which achieves the bound in (2).

Let us first try to familiarize the reader with the statement of the theorem. We have γi=isubscript𝛾𝑖𝑖\gamma_{i}=i for i=1,,k3𝑖1𝑘3i=1,\ldots,k-3. Indeed, for 1γ<nk11𝛾𝑛𝑘11\leq\gamma<n-k-1 we have γ=(nk1nk1)+(nk2nk2)++(nkγnkγ)𝛾binomial𝑛𝑘1𝑛𝑘1binomial𝑛𝑘2𝑛𝑘2binomial𝑛𝑘𝛾𝑛𝑘𝛾\gamma={n-k-1\choose n-k-1}+{n-k-2\choose n-k-2}+\ldots+{n-k-\gamma\choose n-k-\gamma}. Thus, for any such γ𝛾\gamma we have Tγ=[k+1,k+γ]subscript𝑇𝛾𝑘1𝑘𝛾T_{\gamma}=[k+1,k+\gamma] and Sγ=[2,k]{γ}subscript𝑆𝛾2𝑘𝛾S_{\gamma}=[2,k]\cup\{\gamma\}. Thus, the first condition of the definition of a resistant number is satisfied if γk1𝛾𝑘1\gamma\leq k-1. However, the second condition is only satisfied when k+γ>2γ+2𝑘𝛾2𝛾2k+\gamma>2\gamma+2, which is equivalent to γk3𝛾𝑘3\gamma\leq k-3 (or when k=3𝑘3k=3, γ=1𝛾1\gamma=1). From the discussion above we also get that for k>3𝑘3k>3 γk2=(nknk1)=nk.subscript𝛾𝑘2binomial𝑛𝑘𝑛𝑘1𝑛𝑘\gamma_{k-2}={n-k\choose n-k-1}=n-k.

Proposition 1.

The bound in Theorem 6 is always at least as strong as the bound in Theorem 2 for intersecting ([n]k)binomialdelimited-[]𝑛𝑘\mathcal{F}\subset{[n]\choose k} with diversity γ()(n4k3)𝛾binomial𝑛4𝑘3\gamma(\mathcal{F})\leq{n-4\choose k-3}.

Proof.

Let us first compare the statement of Theorem 6 with the statement of Theorem 2 for γl:=(nu1nk1)assignsubscript𝛾𝑙binomial𝑛𝑢1𝑛𝑘1\gamma_{l}:={n-u-1\choose n-k-1} with integer u𝑢u. Such γlsubscript𝛾𝑙\gamma_{l} is resistant for any u[3,k]𝑢3𝑘u\in[3,k] (note that (n4k3)binomial𝑛4𝑘3{n-4\choose k-3} is resistant due to the exceptional condition 3 in the definition). Moreover, it is not difficult to see that, if we substitute such γlsubscript𝛾𝑙\gamma_{l} in (2), then we will get the bound

||(n2nk)++(nu1nku+1)+γl=(n1nk)(nu1nku)+(nu1nk1),binomial𝑛2𝑛𝑘binomial𝑛𝑢1𝑛𝑘𝑢1subscript𝛾𝑙binomial𝑛1𝑛𝑘binomial𝑛𝑢1𝑛𝑘𝑢binomial𝑛𝑢1𝑛𝑘1|\mathcal{F}|\leq{n-2\choose n-k}+\ldots+{n-u-1\choose n-k-u+1}+\gamma_{l}={n-1\choose n-k}-{n-u-1\choose n-k-u}+{n-u-1\choose n-k-1},

which is exactly the bound (1). However, we are getting it here in more relaxed assumptions: while we know that this bound is sharp for γ()=γl𝛾subscript𝛾𝑙\gamma(\mathcal{F})=\gamma_{l}, Theorem 6 also tells us that for γ()>γl𝛾subscript𝛾𝑙\gamma(\mathcal{F})>\gamma_{l} the bound would be strictly worse (and provides us with a possibility to extract, how much worse). Moreover, even if γl1<γ()γlsubscript𝛾𝑙1𝛾subscript𝛾𝑙\gamma_{l-1}<\gamma(\mathcal{F})\leq\gamma_{l}, we are still getting the same upper bound.

Moving to the proof of the proposition, the function in the right hand side of (1) monotone decreasing as γ()𝛾\gamma(\mathcal{F}) increases (and thus u𝑢u decreases). Therefore, to show that the bound (2) is stronger than (1), it is sufficient to show it for values γlsubscript𝛾𝑙\gamma_{l}, l=0,,m𝑙0𝑚l=0,\ldots,m. But for each of these values the bound (2) is sharp, so (1) can be only weaker than (2) for these values.

Thus, clearly, Theorem 6 is a strengthening of Theorem 2. ∎

As a matter of fact, we can replace the bound in (1) with any monotone decreasing function of γ()𝛾\gamma(\mathcal{F}), provided that the bound holds for each γlsubscript𝛾𝑙\gamma_{l}.

Finally, let us mention that we state Theorem 6 only for γ()(n4k3)𝛾binomial𝑛4𝑘3\gamma(\mathcal{F})\leq{n-4\choose k-3}, since Theorem 2 already gives us the bound ||(n2k2)+2(n3k2)binomial𝑛2𝑘22binomial𝑛3𝑘2|\mathcal{F}|\leq{n-2\choose k-2}+2{n-3\choose k-2} if γ()(n4k3)𝛾binomial𝑛4𝑘3\gamma(\mathcal{F})\geq{n-4\choose k-3}, and we cannot get any better bound in this range. However, we are going to analyze the cases when the equality in the inequality for |||\mathcal{F}| above can be attained. It is worth mentioning that the intersecting family {F([n]k):|F[3]|2}conditional-set𝐹binomialdelimited-[]𝑛𝑘𝐹delimited-[]32\{F\in{[n]\choose k}:|F\cap[3]|\geq 2\} attains the bound above on the cardinality, and has diversity (n3k2)binomial𝑛3𝑘2{n-3\choose k-2}. We also note that in a recent work [23] the author managed to prove that for n>ck𝑛𝑐𝑘n>ck with some constant independent of k𝑘k there are no intersecting families ([n]k)binomialdelimited-[]𝑛𝑘\mathcal{F}\subset{[n]\choose k} with diversity bigger than (n3k2)binomial𝑛3𝑘2{n-3\choose k-2}.

Our next goal is to state the “conceptual” version of Theorem 6. We will need certain preparations. We will use the framework and some of the ideas from [9], as well as from [24]. First of all, we pass to the cross-intersecting setting in a standard way: given an intersecting family \mathcal{F}, we consider two families

(1):=assign1absent\displaystyle\mathcal{F}(1):= {F{1}:1F}andconditional-set𝐹11𝐹and\displaystyle\{F\setminus\{1\}:1\in F\in\mathcal{F}\}\ \ \ \ \ \text{and}
(1¯):=assign¯1absent\displaystyle\mathcal{F}(\bar{1}):= {F:1F},conditional-set𝐹1𝐹\displaystyle\{F:1\notin F\in\mathcal{F}\},

and, applying Theorem 4, from now on and until the end of the section assume that (1)=(|(1)|,k1),(1¯)=(|(1¯)|,k)formulae-sequence11𝑘1¯1¯1𝑘\mathcal{F}(1)=\mathcal{L}(|\mathcal{F}(1)|,k-1),\mathcal{F}(\bar{1})=\mathcal{L}(|\mathcal{F}(\bar{1})|,k). Note that (1),(1¯)2[2,n]1¯1superscript22𝑛\mathcal{F}(1),\mathcal{F}(\bar{1})\subset 2^{[2,n]}. For shorthand we denote 𝒜:=(1),:=(1¯)formulae-sequenceassign𝒜1assign¯1{\mathcal{A}}:=\mathcal{F}(1),{\mathcal{B}}:=\mathcal{F}(\bar{1}). In the remaining part dedicated to Theorem 6 we will be mostly working with the set [2,n]2𝑛[2,n], in order not to confuse the reader and to keep clear the relationship between the diversity of intersecting families and the sizes of pairs of cross-intersecting families.

Both 𝒜𝒜{\mathcal{A}} and {\mathcal{B}} are determined by their lexicographically last set. In this section we use lexicographical order on 2[2,n]superscript22𝑛2^{[2,n]}, which is defined as follows: A<B𝐴𝐵A<B iff AB𝐵𝐴A\supset B or the minimal element of AB𝐴𝐵A\setminus B is smaller than the minimal element of BA𝐵𝐴B\setminus A. Let us recall some notions and results from [9] related to the Kruskal-Katona theorem and cross-intersecting families. For a set S[n]𝑆delimited-[]𝑛S\subset[n], 1S1𝑆1\in S and |S[2,n]|a𝑆2𝑛𝑎|S\cap[2,n]|\leq a, we define

(S,a):={A([2,n]a):A<S[2,n]}.assign𝑆𝑎conditional-set𝐴binomial2𝑛𝑎𝐴𝑆2𝑛\mathcal{L}(S,a):=\big{\{}A\in{[2,n]\choose a}:A<S\cap[2,n]\big{\}}.

For example, the family {G([2,n]10):2G,G{3,4}}conditional-set𝐺binomial2𝑛10formulae-sequence2𝐺𝐺34\{G\in{[2,n]\choose 10}:2\in G,G\cap\{3,4\}\neq\emptyset\} is the same as the family (S,10)𝑆10\mathcal{L}(S,10) for S={2,4}𝑆24S=\{2,4\}. If 𝒢=(S,a)𝒢𝑆𝑎\mathcal{G}=\mathcal{L}(S,a) for a certain set S𝑆S, then we say that S𝑆S is the characteristic set of 𝒢𝒢\mathcal{G}. Note that, for convenience, we assume that 1S1𝑆1\in S (motivated by the fact that S𝑆S is the characteristic set for the subfamily of all sets containing 1 in the original family), while T[2,n]𝑇2𝑛T\subset[2,n].

We say that two sets S[n]𝑆delimited-[]𝑛S\subset[n] and T[2,n]𝑇2𝑛T\subset[2,n] form a resistant pair, if the following holds. Assuming that the largest element of T𝑇T is j𝑗j, we have

  1. 1.

    ST={j},ST=[j]formulae-sequence𝑆𝑇𝑗𝑆𝑇delimited-[]𝑗S\cap T=\{j\},\ S\cup T=[j], |S|k,𝑆𝑘|S|\leq k, |T|k𝑇𝑘|T|\leq k;

  2. 2.

    for each 4ij4𝑖𝑗4\leq i\leq j we have |[i]S|<|[i]S|delimited-[]𝑖𝑆delimited-[]𝑖𝑆|[i]\cap S|<|[i]\setminus S| (this condition, roughly speaking, says that in each [i]delimited-[]𝑖[i] there are more elements in T𝑇T than in S𝑆S);

  3. 3.

    For convenience, we include the pair T={2,3,4},S={1,4}formulae-sequence𝑇234𝑆14T=\{2,3,4\},S=\{1,4\} in the list of resistant pairs.

Note that 2 implies that T{2,3,4}234𝑇T\supset\{2,3,4\} for each resistant pair. There is a close relationship between this notion and the notion of a resistant number, which we discuss a bit later. Let us first give the “conceptual” characteristic set version of Theorem 6. For convenience, we put T0=[2,n]subscript𝑇02𝑛T_{0}=[2,n] to correspond to the empty family.

Theorem 7.

Let n>2k6𝑛2𝑘6n>2k\geq 6. Consider all resistant pairs Sl[n],Tl[2,n]formulae-sequencesubscript𝑆𝑙delimited-[]𝑛subscript𝑇𝑙2𝑛S_{l}\subset[n],\ T_{l}\subset[2,n], where l[m]𝑙delimited-[]𝑚l\in[m]. Assume that T0<T1<T2<<Tmsubscript𝑇0subscript𝑇1subscript𝑇2subscript𝑇𝑚T_{0}<T_{1}<T_{2}<\ldots<T_{m}. Then

|(Sl1,k1)|+|(Tl1,k)|>|(Sl,k1)|+|(Tl,k)| for each l[m],formulae-sequencesubscript𝑆𝑙1𝑘1subscript𝑇𝑙1𝑘subscript𝑆𝑙𝑘1subscript𝑇𝑙𝑘 for each 𝑙delimited-[]𝑚|\mathcal{L}(S_{l-1},k-1)|+|\mathcal{L}(T_{l-1},k)|>|\mathcal{L}(S_{l},k-1)|+|\mathcal{L}(T_{l},k)|\ \ \ \text{ for each }l\in[m], (3)

and any cross-intersecting pair of families 𝒜([2,n]k1),([2,n]k)formulae-sequence𝒜binomial2𝑛𝑘1binomial2𝑛𝑘\mathcal{A}\subset{[2,n]\choose k-1},\ \mathcal{B}\subset{[2,n]\choose k} with |(Tl1,k)|<|||(Tl,k)|subscript𝑇𝑙1𝑘subscript𝑇𝑙𝑘|\mathcal{L}(T_{l-1},k)|<|{\mathcal{B}}|\leq|\mathcal{L}(T_{l},k)| satisfies

|𝒜|+|||(Sl,k1)|+|(Tl,k)|.𝒜subscript𝑆𝑙𝑘1subscript𝑇𝑙𝑘|{\mathcal{A}}|+|{\mathcal{B}}|\leq|\mathcal{L}(S_{l},k-1)|+|\mathcal{L}(T_{l},k)|. (4)

In terms of intersecting families, if ([n]k)binomialdelimited-[]𝑛𝑘\mathcal{F}\subset{[n]\choose k} is intersecting and |(Tl1,k)|<γ()|(Tl,k)|subscript𝑇𝑙1𝑘𝛾subscript𝑇𝑙𝑘|\mathcal{L}(T_{l-1},k)|<\gamma(\mathcal{F})\leq|\mathcal{L}(T_{l},k)|, then |||(Sl,k1)|+|(Tl,k)|subscript𝑆𝑙𝑘1subscript𝑇𝑙𝑘|\mathcal{F}|\leq|\mathcal{L}(S_{l},k-1)|+|\mathcal{L}(T_{l},k)|.

First of all, we remark that the intersecting part is clearly equivalent to the second statement of the cross-intersecting part. Second, Proposition 2 below shows that the families L(Sl,k1)𝐿subscript𝑆𝑙𝑘1L(S_{l},k-1) and L(Tl,k)𝐿subscript𝑇𝑙𝑘L(T_{l},k) are cross-intersecting and thus (4) is sharp. Now let us deduce Theorem 6 from Theorem 7.

Reduction of Theorem 6 to Theorem 7.

For any set T[2,n]𝑇2𝑛T\in[2,n] with the largest element sbsubscript𝑠𝑏s_{b} we can compute the size of the family |(T,k1)|\mathcal{L}(T,k-1) as follows. Find the first element b1[2,n]subscript𝑏12𝑛b_{1}\in[2,n], which is missing from T𝑇T, and consider the family with characteristic set T1:=(T[b1]){b1}assignsubscript𝑇1𝑇delimited-[]subscript𝑏1subscript𝑏1T_{1}:=(T\cap[b_{1}])\cup\{b_{1}\}. The size of this family is (nb1kb1+1)=(nb1nk1)binomial𝑛subscript𝑏1𝑘subscript𝑏11binomial𝑛subscript𝑏1𝑛𝑘1{n-b_{1}\choose k-b_{1}+1}={n-b_{1}\choose n-k-1}, since actually T1=[2,b1]subscript𝑇12subscript𝑏1T_{1}=[2,b_{1}]. Since T1<Tsubscript𝑇1𝑇T_{1}<T, this family is a subfamily of (T,k1)𝑇𝑘1\mathcal{L}(T,k-1). At each new step we find the next (not found yet) element bisubscript𝑏𝑖b_{i}, which is missing from T𝑇T, the set Ti:=(T[bi])biassignsubscript𝑇𝑖𝑇delimited-[]subscript𝑏𝑖subscript𝑏𝑖T_{i}:=(T\cap[b_{i}])\cup b_{i}, and count the sets which belong to (Ti,k1)L(Ti1,k1)={F([2,n]k):F[bi]=Ti}subscript𝑇𝑖𝑘1𝐿subscript𝑇𝑖1𝑘1conditional-set𝐹binomial2𝑛𝑘𝐹delimited-[]subscript𝑏𝑖subscript𝑇𝑖\mathcal{L}(T_{i},k-1)\setminus L(T_{i-1},k-1)=\big{\{}F\in{[2,n]\choose k}:F\cap[b_{i}]=T_{i}\big{\}}. Their number is precisely (nbik|Ti|)=(nbink|[bi]Ti|)binomial𝑛subscript𝑏𝑖𝑘subscript𝑇𝑖binomial𝑛subscript𝑏𝑖𝑛𝑘delimited-[]subscript𝑏𝑖subscript𝑇𝑖{n-b_{i}\choose k-|T_{i}|}={n-b_{i}\choose n-k-|[b_{i}]\setminus T_{i}|}. But since we are stopping at every element that is not included in T𝑇T, we get that |[bi]Ti|=|[bi1Ti1|+1==i|[b_{i}]\setminus T_{i}|=|[b_{i-1}\setminus T_{i-1}|+1=\ldots=i. Therefore, the last binomial coefficient is (nbinki)binomial𝑛subscript𝑏𝑖𝑛𝑘𝑖{n-b_{i}\choose n-k-i}. At some point Ti=Tsubscript𝑇𝑖𝑇T_{i}=T, and we stop the procedure, including the sets F([2,n]k1)𝐹binomial2𝑛𝑘1F\in{[2,n]\choose k-1} that satisfy F[sb]=T𝐹delimited-[]subscript𝑠𝑏𝑇F\cap[s_{b}]=T. We get that

|(T,k1)|=(nb1nk1)+(nb2nk2)++(nbsbnsb1),𝑇𝑘1binomial𝑛subscript𝑏1𝑛𝑘1binomial𝑛subscript𝑏2𝑛𝑘2binomial𝑛subscript𝑏subscript𝑠𝑏𝑛subscript𝑠𝑏1|\mathcal{L}(T,k-1)|={n-b_{1}\choose n-k-1}+{n-b_{2}\choose n-k-2}+\ldots+{n-b_{s_{b}}\choose n-s_{b}-1},

the (nk1)𝑛𝑘1(n-k-1)-cascade form! Moreover, we know that the set {b1,,bsb}subscript𝑏1subscript𝑏subscript𝑠𝑏\{b_{1},\ldots,b_{s_{b}}\} is exactly the set Tγsubscript𝑇𝛾T_{\gamma} from before the definition of a resistant number, and we have Tγ=([2,sb]T){sb}subscript𝑇𝛾2subscript𝑠𝑏𝑇subscript𝑠𝑏T_{\gamma}=([2,s_{b}]\setminus T)\cup\{s_{b}\} and thus T=Sγ𝑇subscript𝑆𝛾T=S_{\gamma}.

Therefore, if S,T𝑆𝑇S,T is a resistant pair, then, representing γ:=|(T,k1)|assign𝛾𝑇𝑘1\gamma:=|\mathcal{L}(T,k-1)| in an (nk1)𝑛𝑘1(n-k-1)-cascade form, we get that T=Sγ𝑇subscript𝑆𝛾T=S_{\gamma} and S[2,n]=Tγ𝑆2𝑛subscript𝑇𝛾S\cap[2,n]=T_{\gamma}. This immediately shows that Tγsubscript𝑇𝛾T_{\gamma} and Sγsubscript𝑆𝛾S_{\gamma} satisfy condition 1 of the definition of a resistant number. The implication in the other direction follows in the same way. Condition 2 of the definition of a resistant pair is equivalent to the statement that for each i𝑖i 1+|Tγ[i]|<|[2,i]Tγ|1subscript𝑇𝛾delimited-[]𝑖2𝑖subscript𝑇𝛾1+|T_{\gamma}\cap[i]|<|[2,i]\setminus T_{\gamma}|, which is, in turn, the same as saying bi>2i+2subscript𝑏𝑖2𝑖2b_{i}>2i+2. Finally, it is clear that γ=(n4k3)𝛾binomial𝑛4𝑘3\gamma={n-4\choose k-3} correspond to the characteristic set {2,3,4}234\{2,3,4\}.

We conclude that Tl,Slsubscript𝑇𝑙subscript𝑆𝑙T_{l},S_{l} form a resistant pair if and only if |(Tl,k1)|subscript𝑇𝑙𝑘1|\mathcal{L}(T_{l},k-1)| is a resistant number. Doing calculations as above, one can conclude that

|(Sl,k)|=(na1nk)+(na2nk1)++(nasansa).subscript𝑆𝑙𝑘binomial𝑛subscript𝑎1𝑛𝑘binomial𝑛subscript𝑎2𝑛𝑘1binomial𝑛subscript𝑎subscript𝑠𝑎𝑛subscript𝑠𝑎|\mathcal{L}(S_{l},k)|={n-a_{1}\choose n-k}+{n-a_{2}\choose n-k-1}+\ldots+{n-a_{s_{a}}\choose n-s_{a}}.

Given that, it is clear that the inequality (3) is equivalent to the statement saying that the right hand side of (2) is strictly monotone, and that the (2) is equivalent to (4).

Finally, the sharpness claimed in Theorem 6 follows right away from the fact that the inequality (4) in Theorem 7 is expressed in terms of families. That is, the pair (Sl,k1)subscript𝑆𝑙𝑘1\mathcal{L}(S_{l},k-1) and (Tl,k)subscript𝑇𝑙𝑘\mathcal{L}(T_{l},k) provides us with such an example. ∎

Before proving Theorem 7, let us first shed some light on pairs of cross-intersecting lexicographic families. We say that two sets S𝑆S and T𝑇T in [2,n]2𝑛[2,n] strongly intersect, if there exists a positive integer j𝑗j, such that ST[2,j]={j}𝑆𝑇2𝑗𝑗S\cap T\cap[2,j]=\{j\} and ST[2,j]2𝑗𝑆𝑇S\cup T\supset[2,j]. The following easy proposition was proven in [9]:

Proposition 2 ([9]).

Let A𝐴A and B𝐵B be subsets of [2,n]2𝑛[2,n], |A|a,|B|bformulae-sequence𝐴𝑎𝐵𝑏|A|\leq a,|B|\leq b, and |[2,n]|=n1a+b2𝑛𝑛1𝑎𝑏|[2,n]|=n-1\geq a+b. Then (A,a)𝐴𝑎\mathcal{L}(A,a) and (B,b)𝐵𝑏\mathcal{L}(B,b) are cross-intersecting iff A𝐴A and B𝐵B strongly intersect.

We say that 𝒜([2,n]a)𝒜binomial2𝑛𝑎\mathcal{A}\subset{[2,n]\choose a} and ([2,n]b)binomial2𝑛𝑏\mathcal{B}\subset{[2,n]\choose b} form a maximal cross-intersecting pair, if whenever 𝒜([2,n]a)superscript𝒜binomial2𝑛𝑎\mathcal{A}^{\prime}\subset{[2,n]\choose a} and ([2,n]b)superscriptbinomial2𝑛𝑏\mathcal{B}^{\prime}\subset{[2,n]\choose b} are cross-intersecting with 𝒜𝒜𝒜superscript𝒜\mathcal{A}^{\prime}\supset\mathcal{A} and superscript\mathcal{B}^{\prime}\supset\mathcal{B}, then necessarily 𝒜=𝒜𝒜superscript𝒜\mathcal{A}=\mathcal{A}^{\prime} and =superscript\mathcal{B}=\mathcal{B}^{\prime} holds.

The following proposition from [9] is another important step in our analysis.

Proposition 3 ([9]).

Let a𝑎a and b𝑏b be positive integers, a+bn1𝑎𝑏𝑛1a+b\leq n-1. Let P𝑃P and Q𝑄Q be non-empty subsets of [2,n]2𝑛[2,n] with |P|a𝑃𝑎|P|\leq a, |Q|b𝑄𝑏|Q|\leq b. Suppose that P𝑃P and Q𝑄Q intersect strongly in their last element. That is, there exists j𝑗j, such that PQ={j}𝑃𝑄𝑗P\cap Q=\{j\} and PQ=[2,j]𝑃𝑄2𝑗P\cup Q=[2,j]. Then (P,a)𝑃𝑎\mathcal{L}(P,a) and (Q,b)𝑄𝑏\mathcal{L}(Q,b) form a maximal pair of cross-intersecting families.

Inversely, if (m,a)𝑚𝑎\mathcal{L}(m,a) and (r,b)𝑟𝑏\mathcal{L}(r,b) form a maximal pair of cross-intersecting families, then it is possible to find sets P𝑃P and Q𝑄Q such that (m,a)=(P,a)𝑚𝑎𝑃𝑎\mathcal{L}(m,a)=\mathcal{L}(P,a), (r,b)=(Q,b)𝑟𝑏𝑄𝑏\mathcal{L}(r,b)=\mathcal{L}(Q,b) and P,Q𝑃𝑄P,Q satisfy the above condition.

We note that it may be helpful to interpret the strong intersection property, as well as the lexicographical order etc. in terms of {0,1}01\{0,1\}-vectors: 1 on the i𝑖i-th position if i𝑖i is contained in the corresponding set, and 00 otherwise.

Now we pass on to the proof of the cross-intersecting version of Theorem 7. Fix a cross-intersecting pair of families 𝒜,𝒜{\mathcal{A}},{\mathcal{B}} as in the theorem. There are three important reduction steps, which restrict the class of cross-intersecting families which we need to consider. First, as we have already mentioned, we assume that 𝒜=(S,k1)𝒜𝑆𝑘1{\mathcal{A}}=\mathcal{L}(S,k-1) and =(T,k)𝑇𝑘{\mathcal{B}}=\mathcal{(}T,k) for some characteristic sets S,T𝑆𝑇S,T. Second, in view of Proposition 3, we may assume that 𝒜=(S,k1),=(T,k)formulae-sequence𝒜𝑆𝑘1𝑇𝑘{\mathcal{A}}=\mathcal{L}(S,k-1),\ {\mathcal{B}}=\mathcal{L}(T,k) for some sets S,T𝑆𝑇S,T that strongly intersect in their last element. Note also that |[2,n]|=n1k+(k1)2𝑛𝑛1𝑘𝑘1|[2,n]|=n-1\geq k+(k-1), so we do not have to worry about this condition in the propositions above.

Recall that we aim to maximize |𝒜|+||𝒜|{\mathcal{A}}|+|{\mathcal{B}}| given a lower bound on |||{\mathcal{B}}|. The third reduction step is the following lemma.

Lemma 1.

Consider a pair of cross-intersecting families 𝒜([2,n]k1),([2,n]k)formulae-sequence𝒜binomial2𝑛𝑘1binomial2𝑛𝑘{\mathcal{A}}\subset{[2,n]\choose k-1},\ {\mathcal{B}}\subset{[2,n]\choose k}. Suppose that 𝒜=(S,k1),=(T,k)formulae-sequence𝒜𝑆𝑘1𝑇𝑘{\mathcal{A}}=\mathcal{L}(S,k-1),\ {\mathcal{B}}=\mathcal{L}(T,k) for some sets S[n]𝑆delimited-[]𝑛S\subset[n], T[2,n]𝑇2𝑛T\subset[2,n] that strongly intersect in their last element j𝑗j.

Assume that S𝑆S and T𝑇T do not form a resistant pair, that is, there exists 4ij4𝑖𝑗4\leq i\leq j, such that |[i]S||S[i]|delimited-[]𝑖𝑆𝑆delimited-[]𝑖\big{|}[i]\setminus S\big{|}\leq\big{|}S\cap[i]\big{|}. Put T:=[i]Sassignsuperscript𝑇delimited-[]𝑖𝑆T^{\prime}:=[i]\setminus S and choose Ssuperscript𝑆S^{\prime} so that it strongly intersects with Tsuperscript𝑇T^{\prime} in its largest element. Then the families 𝒜([2,n]k1),([2,n]k)formulae-sequencesuperscript𝒜binomial2𝑛𝑘1binomial2𝑛𝑘{\mathcal{A}}^{\prime}\subset{[2,n]\choose k-1},\ {\mathcal{B}}\subset{[2,n]\choose k} with characteristic sets S,Tsuperscript𝑆superscript𝑇S^{\prime},T^{\prime} are cross-intersecting and satisfy |𝒜|+|||𝒜|+||superscript𝒜superscript𝒜|{\mathcal{A}}^{\prime}|+|{\mathcal{B}}^{\prime}|\geq|{\mathcal{A}}|+|{\mathcal{B}}| and ||>||superscript|{\mathcal{B}}^{\prime}|>|{\mathcal{B}}|.

Moreover, if |[i]S|<|S[i]|delimited-[]𝑖𝑆𝑆delimited-[]𝑖\big{|}[i]\setminus S\big{|}<\big{|}S\cap[i]\big{|}, then we may conclude that |𝒜|+||>|𝒜|+||superscript𝒜superscript𝒜|{\mathcal{A}}^{\prime}|+|{\mathcal{B}}^{\prime}|>|{\mathcal{A}}|+|{\mathcal{B}}|.

Proof of Lemma 1.

First, recall that 1S1𝑆1\in S. Since Ssuperscript𝑆S^{\prime} and Tsuperscript𝑇T^{\prime} are strongly intersecting, the families 𝒜superscript𝒜{\mathcal{A}}^{\prime}, superscript{\mathcal{B}}^{\prime} are cross-intersecting. Next, clearly, TTsuperscript𝑇𝑇T^{\prime}\subsetneq T and thus superscript{\mathcal{B}}^{\prime}\supsetneq{\mathcal{B}}. Therefore, we only have to prove |𝒜|+|||𝒜|+||𝒜superscript𝒜superscript|{\mathcal{A}}|+|{\mathcal{B}}|\leq|{\mathcal{A}}^{\prime}|+|{\mathcal{B}}^{\prime}|.

Consider the following families:

𝒫a:=assignsubscript𝒫𝑎absent\displaystyle\mathcal{P}_{a}:= {P([2,n]k1):P[i]=[2,i]S},conditional-set𝑃binomial2𝑛𝑘1𝑃delimited-[]𝑖2𝑖𝑆\displaystyle\big{\{}P\in{[2,n]\choose k-1}:P\cap[i]=[2,i]\cap S\big{\}},
𝒫b:=assignsubscript𝒫𝑏absent\displaystyle\mathcal{P}_{b}:= {P([2,n]k):P[i]=[i]S}.conditional-set𝑃binomial2𝑛𝑘𝑃delimited-[]𝑖delimited-[]𝑖𝑆\displaystyle\big{\{}P\in{[2,n]\choose k}:P\cap[i]=[i]\setminus S\big{\}}.

Most importantly, we have 𝒜𝒫a=𝒜,𝒜subscript𝒫𝑎superscript𝒜{\mathcal{A}}\setminus\mathcal{P}_{a}={\mathcal{A}}^{\prime}, 𝒫b=subscript𝒫𝑏superscript{\mathcal{B}}\cup\mathcal{P}_{b}={\mathcal{B}}^{\prime}. Let us show, e.g., the first equality. We have S<S<S[i]superscript𝑆𝑆𝑆delimited-[]𝑖S^{\prime}<S<S\cap[i], therefore 𝒜𝒜(S[i],k1)superscript𝒜𝒜𝑆delimited-[]𝑖𝑘1{\mathcal{A}}^{\prime}\subset{\mathcal{A}}\subset\mathcal{L}(S\cap[i],k-1). On the other hand, we claim that Ssuperscript𝑆S^{\prime} and S[i]𝑆delimited-[]𝑖S\cap[i] are two consecutive sets in the lexicographic order on [i]delimited-[]𝑖[i]. Indeed, assume that the largest element of Tsuperscript𝑇T^{\prime} is jsuperscript𝑗j^{\prime}. If j=isuperscript𝑗𝑖j^{\prime}=i, then SS[i]𝑆delimited-[]𝑖superscript𝑆S^{\prime}\supset S\cap[i], (SS)[i]={i}superscript𝑆𝑆delimited-[]𝑖𝑖(S^{\prime}\setminus S)\cap[i]=\{i\}, which proves it in this case. If j<isuperscript𝑗𝑖j^{\prime}<i, then [j+1,i]S[i]superscript𝑗1𝑖𝑆delimited-[]𝑖[j^{\prime}+1,i]\subset S\cap[i], jS[i]superscript𝑗𝑆delimited-[]𝑖j^{\prime}\notin S\cap[i]. It is easy to see that the set that precedes S[i]𝑆delimited-[]𝑖S\cap[i] in the lexicographic order on [i]delimited-[]𝑖[i] “replaces” [j+1,i]superscript𝑗1𝑖[j^{\prime}+1,i] with {j}superscript𝑗\{j^{\prime}\}, that is, it is Ssuperscript𝑆S^{\prime}. Therefore,

𝒜𝒜(S[i],k1)𝒜=(S[i],k1)(S,k1)=𝒫a,𝒜superscript𝒜𝑆delimited-[]𝑖𝑘1superscript𝒜𝑆delimited-[]𝑖𝑘1superscript𝑆𝑘1subscript𝒫𝑎{\mathcal{A}}\setminus{\mathcal{A}}^{\prime}\subset\mathcal{L}(S\cap[i],k-1)\setminus{\mathcal{A}}^{\prime}=\mathcal{L}(S\cap[i],k-1)\setminus\mathcal{L}(S^{\prime},k-1)=\mathcal{P}_{a},

which, together with the fact that 𝒫asubscript𝒫𝑎\mathcal{P}_{a} and 𝒜superscript𝒜{\mathcal{A}}^{\prime} are disjoint, is equivalent to the equality we aimed to prove.

Next, consider a bipartite graph G𝐺G with parts 𝒫a,𝒫bsubscript𝒫𝑎subscript𝒫𝑏\mathcal{P}_{a},\mathcal{P}_{b} and edges connecting disjoint sets. Then, due to the fact that 𝒜𝒜{\mathcal{A}} and {\mathcal{B}} are cross-intersecting, (𝒜𝒫a)(𝒫b)𝒜subscript𝒫𝑎subscript𝒫𝑏({\mathcal{A}}\cap\mathcal{P}_{a})\cup({\mathcal{B}}\cap\mathcal{P}_{b}) is an independent set in G𝐺G.

The graph G𝐺G is biregular, and therefore the largest independent set in G𝐺G is one of its parts. We have |𝒫a|=(nisa)subscript𝒫𝑎binomial𝑛𝑖subscript𝑠𝑎|\mathcal{P}_{a}|={n-i\choose s_{a}}, |𝒫b|=(nisb)subscript𝒫𝑏binomial𝑛𝑖subscript𝑠𝑏|\mathcal{P}_{b}|={n-i\choose s_{b}}, where sa=k|[i]S|,sb=k|[i]S|formulae-sequencesubscript𝑠𝑎𝑘delimited-[]𝑖𝑆subscript𝑠𝑏𝑘delimited-[]𝑖𝑆s_{a}=k-|[i]\cap S|,\ s_{b}=k-|[i]\setminus S|. By the condition from the lemma, we have sbsasubscript𝑠𝑏subscript𝑠𝑎s_{b}\geq s_{a}, and, since nisa+sb𝑛𝑖subscript𝑠𝑎subscript𝑠𝑏n-i\geq s_{a}+s_{b}, we have |𝒫b||𝒫a|subscript𝒫𝑏subscript𝒫𝑎|\mathcal{P}_{b}|\geq|\mathcal{P}_{a}|. We conclude that |𝒫b|subscript𝒫𝑏|\mathcal{P}_{b}| is the largest independent set in G𝐺G, so |𝒫b|(𝒜𝒫a)(𝒫b),subscript𝒫𝑏𝒜subscript𝒫𝑎subscript𝒫𝑏|\mathcal{P}_{b}|\geq({\mathcal{A}}\cap\mathcal{P}_{a})\cup({\mathcal{B}}\cap\mathcal{P}_{b}), and therefore

|𝒜|+||(|𝒜|+||)=|𝒫b||𝒜𝒫a||𝒫b|0.superscript𝒜superscript𝒜subscript𝒫𝑏𝒜subscript𝒫𝑎subscript𝒫𝑏0|{\mathcal{A}}^{\prime}|+|{\mathcal{B}}^{\prime}|-(|{\mathcal{A}}|+|{\mathcal{B}}|)=|\mathcal{P}_{b}|-|{\mathcal{A}}\cap\mathcal{P}_{a}|-|{\mathcal{B}}\cap\mathcal{P}_{b}|\geq 0.

If |[i]S|<|S[i]|delimited-[]𝑖𝑆𝑆delimited-[]𝑖\big{|}[i]\setminus S\big{|}<\big{|}S\cap[i]\big{|}, then |𝒫b|>|𝒫a|subscript𝒫𝑏subscript𝒫𝑎|\mathcal{P}_{b}|>|\mathcal{P}_{a}| and 𝒫bsubscript𝒫𝑏\mathcal{P}_{b} is the unique independent set of maximal size in G𝐺G. Thus, we have strict inequality in the displayed formula above. ∎

Our next goal is to understand how do the resistant pairs behave. More specifically, we aim to show that (3) holds: that sizes of resistant cross-intersecting families are increasing as the size of the second family decreases.

Lemma 2.

Consider a resistant pair of cross-intersecting families 𝒜([2,n]k1),([2,n]k)formulae-sequence𝒜binomial2𝑛𝑘1binomial2𝑛𝑘{\mathcal{A}}\subset{[2,n]\choose k-1},\ {\mathcal{B}}\subset{[2,n]\choose k}, with characteristic sets S,T𝑆𝑇S,T, respectively, and another such resistant pair 𝒜([2,n]k1),([2,n]k)formulae-sequencesuperscript𝒜binomial2𝑛𝑘1superscriptbinomial2𝑛𝑘{\mathcal{A}}^{\prime}\subset{[2,n]\choose k-1},\ {\mathcal{B}}^{\prime}\subset{[2,n]\choose k} with characteristic sets S,Tsuperscript𝑆superscript𝑇S^{\prime},T^{\prime}. Assume also that TT𝑇superscript𝑇T\neq T^{\prime}.

If T<Tsuperscript𝑇𝑇T^{\prime}<T, then ||<||superscript|{\mathcal{B}}^{\prime}|<|{\mathcal{B}}| and |𝒜|+||<|𝒜|+||𝒜superscript𝒜superscript|{\mathcal{A}}|+|{\mathcal{B}}|<|{\mathcal{A}}^{\prime}|+|{\mathcal{B}}^{\prime}|.

Roughly speaking, while for general lexicographic pairs of families the size is not monotone w.r.t. the lexicographic order, it is monotone for resistant pairs, which are maximal with respect to the properties that interest us.

Remark that, since T<Tsuperscript𝑇𝑇T^{\prime}<T, then T{2,3,4}superscript𝑇234T^{\prime}\neq\{2,3,4\} and thus S,Tsuperscript𝑆superscript𝑇S^{\prime},T^{\prime} must satisfy the second condition from the definition of a resistant pair. We also note that we do not use the property that S,T𝑆𝑇S,T form a resistant pair. The proof also works for T=T0(=[2,n])superscript𝑇annotatedsubscript𝑇0absent2𝑛T^{\prime}=T_{0}(=[2,n]).

The proof of this lemma is based on biregular bipartite graphs and is very similar to the proof of Lemma 1, although is a bit trickier.

Proof.

First of all, it is clear that in the conditions of the lemma we have ||<||superscript|{\mathcal{B}}^{\prime}|<|{\mathcal{B}}|. The rest of the proof is concerned with the inequality on the sums of sizes. We will consider two cases depending on how do the sets T𝑇T and Tsuperscript𝑇T^{\prime} relate.

Case 1. TTnot-superset-of-nor-equalssuperscript𝑇𝑇T^{\prime}\nsupseteq T. Find the smallest i𝑖i, such that one of the sets contain i𝑖i, while the other does not. Since T<Tsuperscript𝑇𝑇T^{\prime}<T, we clearly have iT,iTformulae-sequence𝑖superscript𝑇𝑖𝑇i\in T^{\prime},\ i\notin T. Consider the set T′′=T[i]superscript𝑇′′superscript𝑇delimited-[]𝑖T^{\prime\prime}=T^{\prime}\cap[i]. Then we clearly have T<T′′<Tsuperscript𝑇superscript𝑇′′𝑇T^{\prime}<T^{\prime\prime}<T and T′′Tsuperscript𝑇′′superscript𝑇T^{\prime\prime}\subset T^{\prime}. Accordingly, put S′′superscript𝑆′′S^{\prime\prime} to be {i}([i]T′′)𝑖delimited-[]𝑖superscript𝑇′′\{i\}\cup([i]\setminus T^{\prime\prime}), and consider the cross-intersecting families 𝒜′′([2,n]k1),′′([2,n]k)formulae-sequencesuperscript𝒜′′binomial2𝑛𝑘1superscript′′binomial2𝑛𝑘{\mathcal{A}}^{\prime\prime}\subset{[2,n]\choose k-1},\ {\mathcal{B}}^{\prime\prime}\subset{[2,n]\choose k}, which have characteristic vectors S′′superscript𝑆′′S^{\prime\prime} and T′′superscript𝑇′′T^{\prime\prime}, respectively. First, note that 𝒜′′superscript𝒜′′{\mathcal{A}}^{\prime\prime} and ′′superscript′′{\mathcal{B}}^{\prime\prime} is a resistant pair: it follows from the definition of T′′superscript𝑇′′T^{\prime\prime}. We claim that |𝒜′′|+|′′|>|𝒜|+||.superscript𝒜′′superscript′′𝒜|{\mathcal{A}}^{\prime\prime}|+|{\mathcal{B}}^{\prime\prime}|>|{\mathcal{A}}|+|{\mathcal{B}}|.

We prove the inequality above as in Lemma 1, but the roles of S𝑆S and T𝑇T are now switched. Consider a bipartite graph G𝐺G with parts

𝒫a:=assignsubscript𝒫𝑎absent\displaystyle\mathcal{P}_{a}:= {P([2,n]k):P[i]=[2,i]T},conditional-set𝑃binomial2𝑛𝑘𝑃delimited-[]𝑖2𝑖𝑇\displaystyle\big{\{}P\in{[2,n]\choose k}:P\cap[i]=[2,i]\setminus T\big{\}},
𝒫b:=assignsubscript𝒫𝑏absent\displaystyle\mathcal{P}_{b}:= {P([2,n]k):P[i]=[i]T},conditional-set𝑃binomial2𝑛𝑘𝑃delimited-[]𝑖delimited-[]𝑖𝑇\displaystyle\big{\{}P\in{[2,n]\choose k}:P\cap[i]=[i]\cap T\big{\}},

and edges connecting disjoint sets. Similarly, we have 𝒜𝒫a=𝒜′′,𝒜subscript𝒫𝑎superscript𝒜′′{\mathcal{A}}\cup\mathcal{P}_{a}={\mathcal{A}}^{\prime\prime}, 𝒫b=′′subscript𝒫𝑏superscript′′{\mathcal{B}}\setminus\mathcal{P}_{b}={\mathcal{B}}^{\prime\prime}. Indeed, let us verify, e.g., the second equality. All sets P𝑃P such that P[i]<T′′𝑃delimited-[]𝑖superscript𝑇′′P\cap[i]<T^{\prime\prime} are in {\mathcal{B}} and in 𝒫bsubscript𝒫𝑏{\mathcal{B}}\setminus\mathcal{P}_{b}, as well as in ′′superscript′′{\mathcal{B}}^{\prime\prime}, since T′′T[i]less-than-and-not-equalssuperscript𝑇′′𝑇delimited-[]𝑖T^{\prime\prime}\lneq T\cap[i]. On the other hand, if we restrict to [i]delimited-[]𝑖[i], the sets T[i]𝑇delimited-[]𝑖T\cap[i] and T′′superscript𝑇′′T^{\prime\prime} are consecutive in the lexicographic order, and so any set B𝐵B from {\mathcal{B}} such that B>T′′𝐵superscript𝑇′′B>T^{\prime\prime} must satisfy B[i]=T[i]𝐵delimited-[]𝑖𝑇delimited-[]𝑖B\cap[i]=T\cap[i]. Therefore, ′′𝒫bsuperscript′′subscript𝒫𝑏{\mathcal{B}}\setminus{\mathcal{B}}^{\prime\prime}\subset\mathcal{P}_{b} and 𝒫b=′′subscript𝒫𝑏superscript′′{\mathcal{B}}\setminus\mathcal{P}_{b}=\mathcal{B}^{\prime\prime}.

Since 𝒜𝒜{\mathcal{A}} and {\mathcal{B}} are cross-intersecting, the set (𝒜𝒫a)(𝒫b)𝒜subscript𝒫𝑎subscript𝒫𝑏({\mathcal{A}}\cap\mathcal{P}_{a})\cup({\mathcal{B}}\cap\mathcal{P}_{b}) is independent in G𝐺G. On the other hand, the largest independent set in G𝐺G has size max{|𝒫a|,|𝒫b|}subscript𝒫𝑎subscript𝒫𝑏\max\{|\mathcal{P}_{a}|,|\mathcal{P}_{b}|\}. Since the pair 𝒜,𝒜{\mathcal{A}}, {\mathcal{B}} is resistant (and that i𝑖i is not the last element of T𝑇T), we have that |[i]T|=|[i]S|>|[i]S|=|[i]T|delimited-[]𝑖𝑇delimited-[]𝑖𝑆delimited-[]𝑖𝑆delimited-[]𝑖𝑇|[i]\cap T|=|[i]\setminus S|>|[i]\cap S|=|[i]\setminus T|, which implies |𝒫a|=(ni|[2,i]T|)>(ni|[i]T|)=|𝒫b|subscript𝒫𝑎binomial𝑛𝑖2𝑖𝑇binomial𝑛𝑖delimited-[]𝑖𝑇subscript𝒫𝑏|\mathcal{P}_{a}|={n-i\choose|[2,i]\setminus T|}>{n-i\choose|[i]\cap T|}=|\mathcal{P}_{b}|, and thus 𝒫asubscript𝒫𝑎\mathcal{P}_{a} is the (unique) maximal independent set in G𝐺G. We have

|𝒜′′|+|′′|(|𝒜|+||)=|𝒫a||𝒜𝒫a||𝒫b|>0,superscript𝒜′′superscript′′𝒜subscript𝒫𝑎𝒜subscript𝒫𝑎subscript𝒫𝑏0|{\mathcal{A}}^{\prime\prime}|+|{\mathcal{B}}^{\prime\prime}|-(|{\mathcal{A}}|+|{\mathcal{B}}|)=|\mathcal{P}_{a}|-|{\mathcal{A}}\cap\mathcal{P}_{a}|-|{\mathcal{B}}\cap\mathcal{P}_{b}|>0,

and the desired inequality is proven. Therefore, when comparing Tsuperscript𝑇T^{\prime} and T𝑇T, we may replace T𝑇T with T′′superscript𝑇′′T^{\prime\prime}, or rather assume that TT𝑇superscript𝑇T\subset T^{\prime}. We have reduced Case 1 to the following case.

Case 2. TT𝑇superscript𝑇T^{\prime}\supseteq T. Arguing inductively, we may assume that |TT|=1superscript𝑇𝑇1|T^{\prime}\setminus T|=1, and that TT={i}superscript𝑇𝑇𝑖T^{\prime}\setminus T=\{i\} for some i[2,n]𝑖2𝑛i\in[2,n]. Note that in that case i𝑖i is the last element of T,Ssuperscript𝑇superscript𝑆T^{\prime},S^{\prime}, and that TS={i}superscript𝑇superscript𝑆𝑖T^{\prime}\cap S^{\prime}=\{i\}. Consider a bipartite graph G𝐺G with parts

𝒫a:=assignsubscript𝒫𝑎absent\displaystyle\mathcal{P}_{a}:= {P([2,n]k1):P[i]=S[2,i]},conditional-set𝑃binomial2𝑛𝑘1𝑃delimited-[]𝑖superscript𝑆2𝑖\displaystyle\big{\{}P\in{[2,n]\choose k-1}:P\cap[i]=S^{\prime}\cap[2,i]\big{\}},
𝒫b:=assignsubscript𝒫𝑏absent\displaystyle\mathcal{P}_{b}:= {P([2,n]k):P[i]=[i]S},conditional-set𝑃binomial2𝑛𝑘𝑃delimited-[]𝑖delimited-[]𝑖superscript𝑆\displaystyle\big{\{}P\in{[2,n]\choose k}:P\cap[i]=[i]\setminus S^{\prime}\big{\}},

and edges connecting disjoint sets. As before, we have 𝒜𝒫a=𝒜,𝒜subscript𝒫𝑎superscript𝒜{\mathcal{A}}\cup\mathcal{P}_{a}={\mathcal{A}}^{\prime}, 𝒫b=subscript𝒫𝑏superscript{\mathcal{B}}\setminus\mathcal{P}_{b}={\mathcal{B}}^{\prime}. Using the fact that |[i]S|>|[i]S|delimited-[]𝑖superscript𝑆delimited-[]𝑖superscript𝑆|[i]\setminus S^{\prime}|>|[i]\cap S^{\prime}|, we again conclude that |𝒜|+||>|𝒜|+||superscript𝒜superscript𝒜|{\mathcal{A}}^{\prime}|+|{\mathcal{B}}^{\prime}|>|{\mathcal{A}}|+|{\mathcal{B}}|. ∎

Now let us put the things together.

Proof of Theorem 7.

First of all, (3) follows from Lemma 2. Next, given a pair of cross-intersecting families 𝒜,𝒜{\mathcal{A}},{\mathcal{B}}, we may assume using Proposition 3 that their characteristic sets S,T𝑆𝑇S,T strongly intersect in their last coordinate. Using Lemma 1, we may further replace them with a resistant pair 𝒜,superscript𝒜superscript{\mathcal{A}}^{\prime},\ {\mathcal{B}}^{\prime} with characteristic vectors S,Tsuperscript𝑆superscript𝑇S^{\prime},\ T^{\prime}, such that T<T𝑇superscript𝑇T<T^{\prime}. Therefore, if Tl1<Tsubscript𝑇𝑙1𝑇T_{l-1}<T and Tl1Tsubscript𝑇𝑙1𝑇T_{l-1}\neq T, then Tl<Tsubscript𝑇𝑙superscript𝑇T_{l}<T^{\prime}, and therefore the pair (Sl,k1),(Tl,k)subscript𝑆𝑙𝑘1subscript𝑇𝑙𝑘\mathcal{L}(S_{l},k-1),\ \mathcal{L}(T_{l},k) has at least as big sum of cardinalities as 𝒜superscript𝒜{\mathcal{A}}^{\prime} and superscript{\mathcal{B}}^{\prime}. This completes the proof of the theorem.

We only have to add that, although Tm={2,3,4},Sm={1,4}formulae-sequencesubscript𝑇𝑚234subscript𝑆𝑚14T_{m}=\{2,3,4\},S_{m}=\{1,4\} do not satisfy the second requirement of the definition of a resistant pair, it does not pose any problems. We still may apply Lemma 2 to this pair. Moreover, if initially the characteristic set T𝑇T of the family 𝒜𝒜{\mathcal{A}} satisfies Tm1<T<Tmsubscript𝑇𝑚1𝑇subscript𝑇𝑚T_{m-1}<T<T_{m}, then, using Lemma 1 it would be eventually reduced to Tmsubscript𝑇𝑚T_{m}, and thus we may apply it as in other cases. ∎

Let us discuss some possible strengthenings and generalizations of Theorems 6 and 7. First of all, let us determine, for which T𝑇T, Tl1<T<Tlsubscript𝑇𝑙1𝑇subscript𝑇𝑙T_{l-1}<T<T_{l}, it is possible to have equality in (4), given that 𝒜,𝒜\mathcal{A},{\mathcal{B}} are determined by a strongly intersecting pair of sets S,T𝑆𝑇S,\ T, |S|,|T|k𝑆𝑇𝑘|S|,|T|\leq k, which intersect in their last element. We say that a pair of strongly intersecting sets S,T𝑆𝑇S,\ T as above is Tlsubscript𝑇𝑙T_{l}-neutral, if T𝑇T is obtained in the following recursive way:

  1. 1.

    Tlsubscript𝑇𝑙T_{l} is Tlsubscript𝑇𝑙T_{l}-neutral;

  2. 2.

    If Tsuperscript𝑇T^{\prime} is Tlsubscript𝑇𝑙T_{l}-neutral, then the set T:=T{x}assign𝑇superscript𝑇𝑥T:=T^{\prime}\cup\{x\} is Tlsubscript𝑇𝑙T_{l}-neutral, where x=2|T|𝑥2superscript𝑇x=2|T^{\prime}|.

In practice, this means that, starting from a set Tlsubscript𝑇𝑙T_{l}, we add the element 2|Tl|,2subscript𝑇𝑙2|T_{l}|, and then continue adding every other element.

We remark that it is not difficult to see that any Tlsubscript𝑇𝑙T_{l}-neutral pair S,T𝑆𝑇S,T actually satisfies Tl1<TTlsubscript𝑇𝑙1𝑇subscript𝑇𝑙T_{l-1}<T\leq T_{l}. Let us also note that TT𝑇superscript𝑇T\neq T^{\prime}: indeed, from the definition of a resistant pair, the largest element in Tlsubscript𝑇𝑙T_{l} is at most 2|Tl|2subscript𝑇𝑙2|T_{l}| (actually, it is at most 2|Tl|32subscript𝑇𝑙32|T_{l}|-3 for all l<m𝑙𝑚l<m and equal to 2|Tl|22subscript𝑇𝑙22|T_{l}|-2 in the case l=m𝑙𝑚l=m), and every newly added element (via part 2 of the recursive definition) is bigger by 2 than the previously added element.

Theorem 8.

Let n>2k6𝑛2𝑘6n>2k\geq 6. Consider a pair 𝒜([2,n]k1),([2,n]k)formulae-sequence𝒜binomial2𝑛𝑘1binomial2𝑛𝑘{\mathcal{A}}\subset{[2,n]\choose k-1},\ {\mathcal{B}}\subset{[2,n]\choose k} defined by strongly intersecting sets S,T𝑆𝑇S,T that intersect in their largest element. If Tl1<TTlsubscript𝑇𝑙1𝑇subscript𝑇𝑙T_{l-1}<T\leq T_{l} for some l=0,,m𝑙0𝑚l=0,\ldots,m, then equality in (4) holds if and only if the pair S,T𝑆𝑇S,T is Tlsubscript𝑇𝑙T_{l}-neutral.

Proof.

First, let us show that any Tlsubscript𝑇𝑙T_{l}-neutral pair would have equality in  (4). We do it inductively. It is clear for a pair involving Tlsubscript𝑇𝑙T_{l} itself. Assuming it holds for Tsuperscript𝑇T^{\prime}, let us prove that it holds for T:=T{2|T|}assign𝑇superscript𝑇2superscript𝑇T:=T^{\prime}\cup\{2|T^{\prime}|\}.

Consider the pairs of cross-intersecting families 𝒜,𝒜{\mathcal{A}},{\mathcal{B}}, 𝒜,superscript𝒜superscript{\mathcal{A}}^{\prime},{\mathcal{B}}^{\prime}, corresponding to the Tlsubscript𝑇𝑙T_{l}-neutral pairs of sets S,T𝑆𝑇S,T and S,Tsuperscript𝑆superscript𝑇S^{\prime},T^{\prime}, respectively. Looking in the proof of Lemma 1, given that |𝒫a||𝒫b|subscript𝒫𝑎subscript𝒫𝑏|\mathcal{P}_{a}|\leq|\mathcal{P}_{b}|, the equality in |𝒜|+|||𝒜|+||𝒜superscript𝒜superscript|{\mathcal{A}}|+|{\mathcal{B}}|\leq|{\mathcal{A}}^{\prime}|+|{\mathcal{B}}^{\prime}| occur if and only if, first |𝒫a|=|𝒫b|subscript𝒫𝑎subscript𝒫𝑏|\mathcal{P}_{a}|=|\mathcal{P}_{b}|, and, second, 𝒜𝒜=𝒫a,𝒜superscript𝒜subscript𝒫𝑎{\mathcal{A}}\setminus{\mathcal{A}}^{\prime}=\mathcal{P}_{a}, =𝒫b.superscriptsubscript𝒫𝑏{\mathcal{B}}\setminus{\mathcal{B}}^{\prime}=\mathcal{P}_{b}. Indeed, in a connected biregular bipartite graph there are only two possible independent sets of maximal size: its parts.

Consider the set T=T{x}𝑇superscript𝑇𝑥T=T^{\prime}\cup\{x\} and the corresponding set S𝑆S. By the definition of a neutral set, we have

|[x]S|=|[x]S|.delimited-[]𝑥𝑆delimited-[]𝑥𝑆|[x]\cap S|=|[x]\setminus S|.

Therefore, applying the argument of Lemma 1 with

𝒫a:=assignsubscript𝒫𝑎absent\displaystyle\mathcal{P}_{a}:= {P([2,n]k1):P[x]=[2,x]S},conditional-set𝑃binomial2𝑛𝑘1𝑃delimited-[]𝑥2𝑥𝑆\displaystyle\big{\{}P\in{[2,n]\choose k-1}:P\cap[x]=[2,x]\cap S\big{\}},
𝒫b:=assignsubscript𝒫𝑏absent\displaystyle\mathcal{P}_{b}:= {P([2,n]k):P[x]=[x]S},conditional-set𝑃binomial2𝑛𝑘𝑃delimited-[]𝑥delimited-[]𝑥𝑆\displaystyle\big{\{}P\in{[2,n]\choose k}:P\cap[x]=[x]\setminus S\big{\}},

We get that k1|[2,x]S|=k|[x]S|𝑘12𝑥𝑆𝑘delimited-[]𝑥𝑆k-1-|[2,x]\cap S|=k-|[x]\setminus S|, which implies |𝒫a|=|𝒫b|subscript𝒫𝑎subscript𝒫𝑏|\mathcal{P}_{a}|=|\mathcal{P}_{b}|. Moreover, 𝒜𝒜=𝒫a,𝒜superscript𝒜subscript𝒫𝑎{\mathcal{A}}\setminus{\mathcal{A}}^{\prime}=\mathcal{P}_{a}, =𝒫b,superscriptsubscript𝒫𝑏{\mathcal{B}}\setminus{\mathcal{B}}^{\prime}=\mathcal{P}_{b}, since the sets Ssuperscript𝑆S^{\prime} and S𝑆S are consecutive in the lexicographical order on [x]delimited-[]𝑥[x], and the same for T,T𝑇superscript𝑇T,T^{\prime}. Therefore, |𝒜|+||=|𝒜|+||superscript𝒜superscript𝒜|{\mathcal{A}}^{\prime}|+|{\mathcal{B}}^{\prime}|=|{\mathcal{A}}|+|{\mathcal{B}}|.

In the other direction, take a set T𝑇T, Tl1<TTlsubscript𝑇𝑙1𝑇subscript𝑇𝑙T_{l-1}<T\leq T_{l}, and its pair S𝑆S. Consider the corresponding pair of cross-intersecting families 𝒜,𝒜{\mathcal{A}},{\mathcal{B}}. Then it is easy to see that TTlsubscript𝑇𝑙𝑇T\supset T_{l}. (Otherwise, either T>Tl𝑇subscript𝑇𝑙T>T_{l}, or T𝑇T must contain and thus precede some other resistant set, which precedes Tlsubscript𝑇𝑙T_{l}, and this would contradict the position of T𝑇T in the ordering.) Assuming that x𝑥x is the last element in T𝑇T, we must have

|[i]S|<|[i]S|for 4ix1.formulae-sequencedelimited-[]𝑖𝑆delimited-[]𝑖𝑆for 4𝑖𝑥1|[i]\cap S|<|[i]\setminus S|\ \ \ \ \ \ \ \text{for }4\leq i\leq x-1.

Indeed, otherwise, considering the bipartite graph G𝐺G with parts 𝒫asubscript𝒫𝑎\mathcal{P}_{a}, 𝒫bsubscript𝒫𝑏\mathcal{P}_{b} as displayed above for that i𝑖i, we would get that |𝒫a||𝒫b|subscript𝒫𝑎subscript𝒫𝑏|\mathcal{P}_{a}|\leq|\mathcal{P}_{b}| and both 𝒫a𝒜subscript𝒫𝑎𝒜\mathcal{P}_{a}\cap{\mathcal{A}} and 𝒫bsubscript𝒫𝑏\mathcal{P}_{b}\cap{\mathcal{B}} are non-empty. In this case |𝒫a𝒜|+|𝒫b|<|𝒫a|subscript𝒫𝑎𝒜subscript𝒫𝑏subscript𝒫𝑎|\mathcal{P}_{a}\cap{\mathcal{A}}|+|\mathcal{P}_{b}\cap{\mathcal{B}}|<|\mathcal{P}_{a}|, which means that the pair 𝒜,superscript𝒜superscript{\mathcal{A}}^{\prime},{\mathcal{B}}^{\prime} defined by the characteristic sets T:=T[i]assignsuperscript𝑇𝑇delimited-[]𝑖T^{\prime}:=T\cap[i] and its pair Ssuperscript𝑆S^{\prime} would satisfy |𝒜|+||>|𝒜|+||superscript𝒜superscript𝒜|{\mathcal{A}}^{\prime}|+|{\mathcal{B}}^{\prime}|>|{\mathcal{A}}|+|{\mathcal{B}}|. Moreover, TTlsubscript𝑇𝑙superscript𝑇T^{\prime}\supset T_{l}, so T<TTl𝑇superscript𝑇subscript𝑇𝑙T<T^{\prime}\leq T_{l} and |𝒜|+|||(Sl,k1)|+|(Tl,k)|superscript𝒜superscriptsubscript𝑆𝑙𝑘1subscript𝑇𝑙𝑘|{\mathcal{A}}^{\prime}|+|{\mathcal{B}}^{\prime}|\leq|\mathcal{L}(S_{l},k-1)|+|\mathcal{L}(T_{l},k)|. This would contradict the equality in (4).

Therefore, since S,T𝑆𝑇S,T are not resistant, we have

|[x]S|=|[x]S|.delimited-[]𝑥𝑆delimited-[]𝑥𝑆|[x]\cap S|=|[x]\setminus S|.

(We cannot have “>>”, since otherwise we would have “\geq” for i=x1𝑖𝑥1i=x-1.) Removing x𝑥x, we get a set Tsuperscript𝑇T^{\prime}, and conclude that x=2|T|𝑥2superscript𝑇x=2|T^{\prime}|. By induction on the size of the set T𝑇T, we may assume that Tsuperscript𝑇T^{\prime} is Tlsubscript𝑇𝑙T_{l}-neutral. But then T𝑇T is Tlsubscript𝑇𝑙T_{l}-neutral as well. ∎

A slight modification of this argument (with an extension of the definition of a neutral pair to the ones that start with Tm+1:={2,3}assignsubscript𝑇𝑚123T_{m+1}:=\{2,3\}) gives the following:

Proposition 4.

Let n>2k6𝑛2𝑘6n>2k\geq 6. For any intersecting ([n]k)binomialdelimited-[]𝑛𝑘\mathcal{F}\subset{[n]\choose k} with (n4k3)<γ()<(n3k2)binomial𝑛4𝑘3𝛾binomial𝑛3𝑘2{n-4\choose k-3}<\gamma(\mathcal{F})<{n-3\choose k-2} we have ||<(n2k2)+2(n3k2)binomial𝑛2𝑘22binomial𝑛3𝑘2|\mathcal{F}|<{n-2\choose k-2}+2{n-3\choose k-2}.

Recall that there are intersecting families ([n]k)binomialdelimited-[]𝑛𝑘\mathcal{F}\subset{[n]\choose k} for both γ()=(n4k3)𝛾binomial𝑛4𝑘3\gamma(\mathcal{F})={n-4\choose k-3} and (n3k2)binomial𝑛3𝑘2{n-3\choose k-2} that have size (n2k2)+2(n3k2)binomial𝑛2𝑘22binomial𝑛3𝑘2{n-2\choose k-2}+2{n-3\choose k-2}.

Next, our techniques allow us to give a weighted version of Theorems 6 and 7. Assume that, instead of maximising the expression ||=Δ()+γ()Δ𝛾|\mathcal{F}|=\Delta(\mathcal{F})+\gamma(\mathcal{F}) with a given lower bound on γ()𝛾\gamma(\mathcal{F}), we are maximising the expression Δ()+cγ()Δ𝑐𝛾\Delta(\mathcal{F})+c\gamma(\mathcal{F}) with some c>1𝑐1c>1. (In terms of cross-intersecting families, we are maximising the expression |𝒜|+c||𝒜𝑐|{\mathcal{A}}|+c|{\mathcal{B}}|.) Then the following is true.

Theorem 9.

Let n>2k6𝑛2𝑘6n>2k\geq 6. Consider all resistant pairs Sl[n],Tl[2,n]formulae-sequencesubscript𝑆𝑙delimited-[]𝑛subscript𝑇𝑙2𝑛S_{l}\subset[n],\ T_{l}\subset[2,n], where l=0,,m𝑙0𝑚l=0,\ldots,m. Assume that T0<T1<T2<<Tmsubscript𝑇0subscript𝑇1subscript𝑇2subscript𝑇𝑚T_{0}<T_{1}<T_{2}<\ldots<T_{m}. Put C:=nk3k3>1assign𝐶𝑛𝑘3𝑘31C:=\frac{n-k-3}{k-3}>1. Then

|(Sl1,k1)|+C|(Tl1,k)||(Sl,k1)|+C|(Tl,k)| for each l[m],formulae-sequencesubscript𝑆𝑙1𝑘1𝐶subscript𝑇𝑙1𝑘subscript𝑆𝑙𝑘1𝐶subscript𝑇𝑙𝑘 for each 𝑙delimited-[]𝑚|\mathcal{L}(S_{l-1},k-1)|+C|\mathcal{L}(T_{l-1},k)|\geq|\mathcal{L}(S_{l},k-1)|+C|\mathcal{L}(T_{l},k)|\ \ \ \text{ for each }l\in[m], (5)

and any cross-intersecting pair of families 𝒜([2,n]k1),([2,n]k)formulae-sequence𝒜binomial2𝑛𝑘1binomial2𝑛𝑘\mathcal{A}\subset{[2,n]\choose k-1},\ \mathcal{B}\subset{[2,n]\choose k} with |(Tl1,k)|<|||(Tl,k)|subscript𝑇𝑙1𝑘subscript𝑇𝑙𝑘|\mathcal{L}(T_{l-1},k)|<|{\mathcal{B}}|\leq|\mathcal{L}(T_{l},k)| satisfies |𝒜|+C|||(Sl,k1)|+C|(Tl,k)|𝒜𝐶subscript𝑆𝑙𝑘1𝐶subscript𝑇𝑙𝑘|{\mathcal{A}}|+C|{\mathcal{B}}|\leq|\mathcal{L}(S_{l},k-1)|+C|\mathcal{L}(T_{l},k)|.

In terms of intersecting families, if ([n]k)binomialdelimited-[]𝑛𝑘\mathcal{F}\subset{[n]\choose k} is intersecting and |(Tl1,k)|<γ()|(Tl,k)|subscript𝑇𝑙1𝑘𝛾subscript𝑇𝑙𝑘|\mathcal{L}(T_{l-1},k)|<\gamma(\mathcal{F})\leq|\mathcal{L}(T_{l},k)|, then Δ()+Cγ()|(Sl,k1)|+C|(Tl,k)|Δ𝐶𝛾subscript𝑆𝑙𝑘1𝐶subscript𝑇𝑙𝑘\Delta(\mathcal{F})+C\gamma(\mathcal{F})\leq|\mathcal{L}(S_{l},k-1)|+C|\mathcal{L}(T_{l},k)|.

Proof.

The proof of this theorem follows the same steps as the proof of Theorem 7. We sketch the proof of the cross-intersecting version of the theorem. Using Lemma 1, we may assume that 𝒜𝒜{\mathcal{A}} and {\mathcal{B}} form a resistant pair (indeed, otherwise, replacing 𝒜,𝒜{\mathcal{A}},\ {\mathcal{B}} with 𝒜|,{\mathcal{A}}^{\prime}|, ||{\mathcal{B}}^{\prime} which satisfy |𝒜|+|||𝒜|+||superscript𝒜superscript𝒜|{\mathcal{A}}^{\prime}|+|{\mathcal{B}}^{\prime}|\geq|{\mathcal{A}}|+|{\mathcal{B}}|, ||>||superscript|{\mathcal{B}}^{\prime}|>|{\mathcal{B}}| definitely increases the value of |𝒜|+C||𝒜𝐶|{\mathcal{A}}|+C|{\mathcal{B}}|). Then, looking at the proof of Lemma 2, we see that in each of the cases the bipartite graph G𝐺G had parts of sizes (nisa)binomial𝑛𝑖subscript𝑠𝑎{n-i\choose s_{a}}, (nisb)binomial𝑛𝑖subscript𝑠𝑏{n-i\choose s_{b}}, where sa+sb=2kisubscript𝑠𝑎subscript𝑠𝑏2𝑘𝑖s_{a}+s_{b}=2k-i and sa>sbsubscript𝑠𝑎subscript𝑠𝑏s_{a}>s_{b}. We also know that sbk3subscript𝑠𝑏𝑘3s_{b}\leq k-3. Therefore, even if we put weight (nisa)/(nisb)binomial𝑛𝑖subscript𝑠𝑎binomial𝑛𝑖subscript𝑠𝑏{n-i\choose s_{a}}/{n-i\choose s_{b}} on each vertex of the part 𝒫bsubscript𝒫𝑏\mathcal{P}_{b} and weight 1 on each vertex of the part 𝒫asubscript𝒫𝑎\mathcal{P}_{a}, we can still conclude that the independent set of the largest weight in G𝐺G is 𝒫asubscript𝒫𝑎\mathcal{P}_{a}, and the rest of the argument works out as before. We have

(nisa)(nisb)(nisb)sa=(n2k+sa)sa(nk3)k3.binomial𝑛𝑖subscript𝑠𝑎binomial𝑛𝑖subscript𝑠𝑏𝑛𝑖subscript𝑠𝑏subscript𝑠𝑎𝑛2𝑘subscript𝑠𝑎subscript𝑠𝑎𝑛𝑘3𝑘3\frac{{n-i\choose s_{a}}}{{n-i\choose s_{b}}}\geq\frac{(n-i-s_{b})}{s_{a}}=\frac{(n-2k+s_{a})}{s_{a}}\geq\frac{(n-k-3)}{k-3}. (6)

Therefore, substituting nk3k3𝑛𝑘3𝑘3\frac{n-k-3}{k-3} as the weight in the 𝒫bsubscript𝒫𝑏\mathcal{P}_{b} part will work. ∎

Corollary 1.

Let n>2k6𝑛2𝑘6n>2k\leq 6. For any intersecting family ([n]k),binomialdelimited-[]𝑛𝑘\mathcal{F}\subset{[n]\choose k}, γ()(n4k3)𝛾binomial𝑛4𝑘3\gamma(\mathcal{F})\leq{n-4\choose k-3}, we have |Δ()|+nk3k3γ()(n1k1)Δ𝑛𝑘3𝑘3𝛾binomial𝑛1𝑘1|\Delta(\mathcal{F})|+\frac{n-k-3}{k-3}\gamma(\mathcal{F})\leq{n-1\choose k-1}.

If, additionally, \mathcal{F} is non-trivial, then |Δ()|+nk3k3γ()(n1k1)(nk1k1)+nk3k3Δ𝑛𝑘3𝑘3𝛾binomial𝑛1𝑘1binomial𝑛𝑘1𝑘1𝑛𝑘3𝑘3|\Delta(\mathcal{F})|+\frac{n-k-3}{k-3}\gamma(\mathcal{F})\leq{n-1\choose k-1}-{n-k-1\choose k-1}+\frac{n-k-3}{k-3}.

Is not difficult extend the considerations of this section to the case of cross-intersecting families 𝒜([n]a),([n]b)formulae-sequence𝒜binomialdelimited-[]𝑛𝑎binomialdelimited-[]𝑛𝑏{\mathcal{A}}\subset{[n]\choose a},{\mathcal{B}}\subset{[n]\choose b}, a<b𝑎𝑏a<b. The wording of Theorem 7 would stay practically the same. One just need to adjust the definition of a resistant pair. Note that, unlike before in this section, here we will work with cross-intersecting families on [n]delimited-[]𝑛[n] (and not [2,n]2𝑛[2,n]).

We say that two sets S,T[n]𝑆𝑇delimited-[]𝑛S,T\subset[n] form an (a,b)𝑎𝑏(a,b)-resistant pair, if the following holds. Assuming that the largest element of T𝑇T is j𝑗j, we have

  1. 1.

    ST={j},ST=[j]formulae-sequence𝑆𝑇𝑗𝑆𝑇delimited-[]𝑗S\cap T=\{j\},\ S\cup T=[j], |S|a,𝑆𝑎|S|\leq a, |T|b𝑇𝑏|T|\leq b;

  2. 2.

    for each ba+2ij𝑏𝑎2𝑖𝑗b-a+2\leq i\leq j we have |[i]S|a<|[i]S|bdelimited-[]𝑖𝑆𝑎delimited-[]𝑖𝑆𝑏|[i]\cap S|-a<|[i]\setminus S|-b;

  3. 3.

    The pair T={1,,ba+2},S={1,ba+2}formulae-sequence𝑇1𝑏𝑎2𝑆1𝑏𝑎2T=\{1,\ldots,b-a+2\},S=\{1,b-a+2\} is resistant.

Again, for convenience, we put T0=[2,n]subscript𝑇02𝑛T_{0}=[2,n] to correspond to the empty family and Tm+1={1,ba+1}subscript𝑇𝑚11𝑏𝑎1T_{m+1}=\{1,b-a+1\} to be an analogue of the set {2,3}23\{2,3\} in this case, where m𝑚m is the number of resistant pairs. Here is the theorem, which is an analogue of Theorems 789 and Proposition 4 in the case of general cross-intersecting families. Its proof is a straightforward generalization of the proofs of the respective theorems, thus we omit it.

Theorem 10.

Let a,b>0𝑎𝑏0a,b>0, n>a+b𝑛𝑎𝑏n>a+b. Consider all (a,b)𝑎𝑏(a,b)-resistant pairs Sl[n],Tl[2,n]formulae-sequencesubscript𝑆𝑙delimited-[]𝑛subscript𝑇𝑙2𝑛S_{l}\subset[n],\ T_{l}\subset[2,n], where l[m]𝑙delimited-[]𝑚l\in[m]. Assume that T0<T1<T2<<Tm<Tm+1subscript𝑇0subscript𝑇1subscript𝑇2subscript𝑇𝑚subscript𝑇𝑚1T_{0}<T_{1}<T_{2}<\ldots<T_{m}<T_{m+1}.

1. Then

|(Sl1,a)|+|(Tl1,b)|>|(Sl,a)|+|(Tl,b)| for each l[m],formulae-sequencesubscript𝑆𝑙1𝑎subscript𝑇𝑙1𝑏subscript𝑆𝑙𝑎subscript𝑇𝑙𝑏 for each 𝑙delimited-[]𝑚|\mathcal{L}(S_{l-1},a)|+|\mathcal{L}(T_{l-1},b)|>|\mathcal{L}(S_{l},a)|+|\mathcal{L}(T_{l},b)|\ \ \ \text{ for each }l\in[m], (7)

and any cross-intersecting pair of families 𝒜([n]a),([n]b)formulae-sequence𝒜binomialdelimited-[]𝑛𝑎binomialdelimited-[]𝑛𝑏\mathcal{A}\subset{[n]\choose a},\ \mathcal{B}\subset{[n]\choose b} with |(Tl1,b)|<|||(Tl,b)|subscript𝑇𝑙1𝑏subscript𝑇𝑙𝑏|\mathcal{L}(T_{l-1},b)|<|{\mathcal{B}}|\leq|\mathcal{L}(T_{l},b)| satisfies

|𝒜|+|||(Sl,a)|+|(Tl,b)|.𝒜subscript𝑆𝑙𝑎subscript𝑇𝑙𝑏|{\mathcal{A}}|+|{\mathcal{B}}|\leq|\mathcal{L}(S_{l},a)|+|\mathcal{L}(T_{l},b)|. (8)

With an obvious generalization of the notion of a neutral pair, if the families (|𝒜|,a)𝒜𝑎\mathcal{L}(|{\mathcal{A}}|,a), (||,b)𝑏\mathcal{L}(|{\mathcal{B}}|,b) have characteristic sets S,T𝑆𝑇S,T, then we have equality in (8) if and only if S,T𝑆𝑇S,T is a Tlsubscript𝑇𝑙T_{l}-neutral pair.

2. The same conclusion could be made with |||\mathcal{B}|, |(Tl1,b)|subscript𝑇𝑙1𝑏|\mathcal{L}(T_{l-1},b)| |(Tl,b)|subscript𝑇𝑙𝑏|\mathcal{L}(T_{l},b)| replaced with C||𝐶C|\mathcal{B}|, C|(Tl1,b)|𝐶subscript𝑇𝑙1𝑏C|\mathcal{L}(T_{l-1},b)| C|(Tl,b)|𝐶subscript𝑇𝑙𝑏C|\mathcal{L}(T_{l},b)|, where C𝐶C is a constant, C<nb2a2.𝐶𝑛𝑏2𝑎2C<\frac{n-b-2}{a-2}.

3. Denote t:=ab1assign𝑡𝑎𝑏1t:=a-b-1. For (n+t1a2)<||<(n+ta1)binomial𝑛𝑡1𝑎2binomial𝑛𝑡𝑎1{n+t-1\choose a-2}<|{\mathcal{B}}|<{n+t\choose a-1} we have

|𝒜|+||<(na)(n+ta)+(n+ta1)=(na)(n+t1a)+(n+t1a2).𝒜binomial𝑛𝑎binomial𝑛𝑡𝑎binomial𝑛𝑡𝑎1binomial𝑛𝑎binomial𝑛𝑡1𝑎binomial𝑛𝑡1𝑎2|{\mathcal{A}}|+|{\mathcal{B}}|<{n\choose a}-{n+t\choose a}+{n+t\choose a-1}={n\choose a}-{n+t-1\choose a}+{n+t-1\choose a-2}.

For both Tm+1=[b+1a]subscript𝑇𝑚1delimited-[]𝑏1𝑎T_{m+1}=[b+1-a], Tm=[b+2a]subscript𝑇𝑚delimited-[]𝑏2𝑎T_{m}=[b+2-a] and the corresponding Sm+1,Smsubscript𝑆𝑚1subscript𝑆𝑚S_{m+1},\ S_{m} we have equality in the inequality above for (Si,a),(Ti,b)subscript𝑆𝑖𝑎subscript𝑇𝑖𝑏\mathcal{L}(S_{i},a),\mathcal{L}(T_{i},b), i=m,m+1𝑖𝑚𝑚1i=m,m+1 (note that the second family has cardinality (n+ta1)binomial𝑛𝑡𝑎1{n+t\choose a-1} and (n+t1a2)binomial𝑛𝑡1𝑎2{n+t-1\choose a-2}, respectively).

This theorem generalizes and strengthens many results on cross-intersecting families, in particular, the theorem for cross-intersecting families proven in [24] and the following theorem due to Frankl and Tokushige [12]

Theorem 11 (Frankl, Tokushige, [12]).

Let n>a+b𝑛𝑎𝑏n>a+b, ab𝑎𝑏a\leq b, and suppose that families ([n]a),𝒢([n]b)formulae-sequencebinomialdelimited-[]𝑛𝑎𝒢binomialdelimited-[]𝑛𝑏\mathcal{F}\subset{[n]\choose a},\mathcal{G}\subset{[n]\choose b} are cross-intersecting. Suppose that for some real number α1𝛼1\alpha\geq 1 we have (nαna)||(n1na)binomial𝑛𝛼𝑛𝑎binomial𝑛1𝑛𝑎{n-\alpha\choose n-a}\leq|\mathcal{F}|\leq{n-1\choose n-a}. Then

||+|𝒢|(nb)+(nαna)(nαb).𝒢binomial𝑛𝑏binomial𝑛𝛼𝑛𝑎binomial𝑛𝛼𝑏|\mathcal{F}|+|\mathcal{G}|\leq{n\choose b}+{n-\alpha\choose n-a}-{n-\alpha\choose b}. (9)

The deduction is similar to the one we made for Theorems 2 from Theorem 6.

One easy corollary of ((7) and part 3 of) Theorem 10, which also appeared in [24] and other places, is as follows:

Corollary 2 ([24]).

Let a,b>0𝑎𝑏0a,b>0, n>a+b𝑛𝑎𝑏n>a+b. Let 𝒜([n]a),([n]b)formulae-sequence𝒜binomialdelimited-[]𝑛𝑎binomialdelimited-[]𝑛𝑏{\mathcal{A}}\subset{[n]\choose a},\ {\mathcal{B}}\subset{[n]\choose b} be a pair of cross-intersecting families. Then, if ||(n+ab1a1)binomial𝑛𝑎𝑏1𝑎1|{\mathcal{B}}|\leq{n+a-b-1\choose a-1}, then

|𝒜|+||(na).𝒜binomial𝑛𝑎|{\mathcal{A}}|+|{\mathcal{B}}|\leq{n\choose a}. (10)

Moreover, the displayed inequality is strict unless ||=00|{\mathcal{B}}|=0.

If (njbj)||(n+ab1a1)binomial𝑛𝑗𝑏𝑗binomial𝑛𝑎𝑏1𝑎1{n-j\choose b-j}\leq|{\mathcal{B}}|\leq{n+a-b-1\choose a-1} for j[ba+1,b]𝑗𝑏𝑎1𝑏j\in[b-a+1,b], then

|𝒜|+||(na)(nja)+(njbj).𝒜binomial𝑛𝑎binomial𝑛𝑗𝑎binomial𝑛𝑗𝑏𝑗|{\mathcal{A}}|+|{\mathcal{B}}|\leq{n\choose a}-{n-j\choose a}+{n-j\choose b-j}. (11)

Moreover, if the left inequality on {\mathcal{B}} is strict, then the inequality in the displayed formula above is also strict.

Note that the values ||=(njbj)binomial𝑛𝑗𝑏𝑗|{\mathcal{B}}|={n-j\choose b-j} correspond to resistant pairs in Theorem 10.

4 Beyond Hilton-Milner theorem

Several authors aimed to determine precisely, what are the largest intersecting families in ([n]k)binomialdelimited-[]𝑛𝑘{[n]\choose k} with certain restrictions. One of such questions was studied by Han and Kohayakawa, who determined precisely, what is the largest family of intersecting families that is neither contained in the Erdős-Ko-Rado family, nor in the Hilton-Milner family. In our terms, the question is simply as follows: what is the largest intersecting family with γ()2𝛾2\gamma(\mathcal{F})\geq 2? The proof of Han and Kohayakawa is quite technical and long. Kruskal-Katona-type arguments allow for a very short and simple proof in the case k5𝑘5k\geq 5. For i[k]𝑖delimited-[]𝑘i\in[k] let us put

𝒥i:=[2,k+1][i+1,k+i]{F([n]k):1F,F[2,k+1],F[i+1,k+i]}.assignsubscript𝒥𝑖2𝑘1𝑖1𝑘𝑖conditional-set𝐹binomialdelimited-[]𝑛𝑘formulae-sequence1𝐹formulae-sequence𝐹2𝑘1𝐹𝑖1𝑘𝑖\mathcal{J}_{i}:=[2,k+1]\cup[i+1,k+i]\cup\big{\{}F\in{[n]\choose k}:1\in F,F\cap[2,k+1]\neq\emptyset,F\cap[i+1,k+i]\neq\emptyset\big{\}}.

We note that 𝒥i([n]k)subscript𝒥𝑖binomialdelimited-[]𝑛𝑘\mathcal{J}_{i}\subset{[n]\choose k} and that 𝒥isubscript𝒥𝑖\mathcal{J}_{i} are intersecting. Moreover, γ(𝒥i)=2𝛾subscript𝒥𝑖2\gamma(\mathcal{J}_{i})=2 for i>1𝑖1i>1 and 𝒥1subscript𝒥1\mathcal{J}_{1} is the Hilton-Milner family.

Theorem 12 ([14]).

Let n>2k𝑛2𝑘n>2k, k4𝑘4k\geq 4. Then any intersecting family \mathcal{F} with γ()2𝛾2\gamma(\mathcal{F})\geq 2 satisfies

||(n1k1)(nk1k1)(nk2k2)+2,binomial𝑛1𝑘1binomial𝑛𝑘1𝑘1binomial𝑛𝑘2𝑘22|\mathcal{F}|\leq{n-1\choose k-1}-{n-k-1\choose k-1}-{n-k-2\choose k-2}+2, (12)

moreover, for k5𝑘5k\geq 5 the equality is attained only on the families isomorphic to 𝒥2subscript𝒥2\mathcal{J}_{2}.

We note that Han and Kohayakawa proved their theorem for k=3𝑘3k=3, and also resolved the uniqueness case for k=4𝑘4k=4. Unfortunately, this cannot be done in a simple way using our methods. A slightly weaker version of the theorem above (without uniqueness) is a consequence of one of the results obtained by Hilton and Milner [16] (see [14]).

It is not so difficult to deduce Theorem 12 from Theorem 4 directly, but using Theorems 6, 7 makes it even easier.

Proof.

In terms of Theorem 6, we know that γi=isubscript𝛾𝑖𝑖\gamma_{i}=i for i[k3]𝑖delimited-[]𝑘3i\in[k-3], and γk2=nksubscript𝛾𝑘2𝑛𝑘\gamma_{k-2}=n-k. Substituting l=2𝑙2l=2 for k5𝑘5k\geq 5 in (2), we get

||(n2nk)+(n3nk1)++(nkn2k+2)+(nk2n2k+1)+2=binomial𝑛2𝑛𝑘binomial𝑛3𝑛𝑘1binomial𝑛𝑘𝑛2𝑘2binomial𝑛𝑘2𝑛2𝑘12absent|\mathcal{F}|\leq{n-2\choose n-k}+{n-3\choose n-k-1}+\ldots+{n-k\choose n-2k+2}+{n-k-2\choose n-2k+1}+2=
(n1nk)(nkn2k+1)+(nk2n2k+1)+2=(n1nk)(nk1n2k)(nk2n2k)+2,binomial𝑛1𝑛𝑘binomial𝑛𝑘𝑛2𝑘1binomial𝑛𝑘2𝑛2𝑘12binomial𝑛1𝑛𝑘binomial𝑛𝑘1𝑛2𝑘binomial𝑛𝑘2𝑛2𝑘2{n-1\choose n-k}-{n-k\choose n-2k+1}+{n-k-2\choose n-2k+1}+2={n-1\choose n-k}-{n-k-1\choose n-2k}-{n-k-2\choose n-2k}+2,

which is exactly the right hand side of (12). We know that this is sharp, due to an example isomorphic to 𝒥2subscript𝒥2\mathcal{J}_{2} (it is also isomorphic to the corresponding example from Theorem 6).

Since the right hand side of (2) strictly decreases as l𝑙l increases, we may conclude that for k5𝑘5k\geq 5 any family \mathcal{F} with γ()>γ2=2𝛾subscript𝛾22\gamma(\mathcal{F})>\gamma_{2}=2 will have strict inequality in (2) with l=2𝑙2l=2, and thus a strict inequality in (12). Moreover, for k=4𝑘4k=4 the lexicographic family with diversity γ2=n4subscript𝛾2𝑛4\gamma_{2}=n-4 has the same cardinality as 𝒥2subscript𝒥2\mathcal{J}_{2}, displayed above (due to Theorem 8, or via direct calculation), and no family with γ>γ1𝛾subscript𝛾1\gamma>\gamma_{1} can have larger cardinality.

Therefore, the bound (12) is proven, and to complete the proof, we should only show that for k5𝑘5k\geq 5 among the intersecting families ([n]k)binomialdelimited-[]𝑛𝑘\mathcal{F}\subset{[n]\choose k} with γ()=2𝛾2\gamma(\mathcal{F})=2 all families achieving equality in (12) are isomorphic to 𝒥2subscript𝒥2\mathcal{J}_{2}. This could be done by a simple computation.

Any (maximal) intersecting family ([n]k)binomialdelimited-[]𝑛𝑘\mathcal{F}\subset{[n]\choose k} with γ()=2𝛾2\gamma(\mathcal{F})=2 is uniquely determined by the intersection of the two sets A,B𝐴𝐵A,B, which are not containing the most popular element, and thus is isomorphic to one of the 𝒥isubscript𝒥𝑖\mathcal{J}_{i}, i[k]𝑖delimited-[]𝑘i\in[k].

Using exclusion-inclusion formula for 𝒥isubscript𝒥𝑖\mathcal{J}_{i}, we conclude that (the number of k𝑘k-sets that contain 1 and do not intersect either A𝐴A or B𝐵B) == (the number of sets that contain 1 and miss A𝐴A) ++ (the number of sets that contain 1 and miss B𝐵B) - (the number of sets that contain 1 and miss both A𝐴A and B𝐵B) =2(nk1k1)(n2k+|AB|1k1)absent2binomial𝑛𝑘1𝑘1binomial𝑛2𝑘𝐴𝐵1𝑘1=2{n-k-1\choose k-1}-{n-2k+|A\cap B|-1\choose k-1}, and this function clearly strictly increases as the intersection size of A𝐴A and B𝐵B decreases, and so we “loose” more and more sets containing 111 as i𝑖i become smaller. Therefore, the unique (up to isomorphism) maximal intersecting family \mathcal{F} with γ()=2𝛾2\gamma(\mathcal{F})=2 is 𝒥2subscript𝒥2\mathcal{J}_{2}. Theorem is proven. ∎

Let us denote lsubscript𝑙\mathcal{F}_{l} the maximal intersecting family with l(1¯)=(l,k)subscript𝑙¯1𝑙𝑘\mathcal{F}_{l}(\bar{1})=\mathcal{L}(l,k). Note that 𝒥2subscript𝒥2\mathcal{J}_{2} is isomorphic to 2subscript2\mathcal{F}_{2}. It is not difficult to see that, in terms of Theorem 7, for l=0,,k3𝑙0𝑘3l=0,\ldots,k-3 we have l(1¯)=(Tl,k)subscript𝑙¯1subscript𝑇𝑙𝑘\mathcal{F}_{l}(\bar{1})=\mathcal{L}(T_{l},k) and, therefore, l(1)=(Sl,k)subscript𝑙1subscript𝑆𝑙𝑘\mathcal{F}_{l}(1)=\mathcal{L}(S_{l},k) (see the analysis after Theorem 7). We also have nk=(Tk2,k)subscript𝑛𝑘subscript𝑇𝑘2𝑘\mathcal{F}_{n-k}=\mathcal{L}(T_{k-2},k). Moreover, it is not difficult to see that for k1<l<nk𝑘1𝑙𝑛𝑘k-1<l<n-k we have lnksubscript𝑙subscript𝑛𝑘\mathcal{F}_{l}\subset\mathcal{F}_{n-k} (indeed, we have l(1)=nk(1)subscript𝑙1subscript𝑛𝑘1\mathcal{F}_{l}(1)=\mathcal{F}_{n-k}(1) for this range). Also, using Theorems 7 and 8 (or by direct calculation), we can conclude that |k1|<|k2|=|nk|subscript𝑘1subscript𝑘2subscript𝑛𝑘|\mathcal{F}_{k-1}|<|\mathcal{F}_{k-2}|=|\mathcal{F}_{n-k}|.

The next theorem is another application of our method.

Theorem 13.

Assume that k5𝑘5k\geq 5 and n>2k𝑛2𝑘n>2k. Consider an intersecting family ([n]k)binomialdelimited-[]𝑛𝑘\mathcal{F}\subset{[n]\choose k}, such that Δ()=δ(1)Δ𝛿1\Delta(\mathcal{F})=\delta(1). Assume that |F(1¯)F|k2subscript𝐹¯1𝐹𝑘2|\cap_{F\in\mathcal{F}(\bar{1})}F|\leq k-2. Then

|||𝒥3|,subscript𝒥3|\mathcal{F}|\leq|\mathcal{J}_{3}|, (13)

with the equality only possible if \mathcal{F} is isomorphic to 𝒥3subscript𝒥3\mathcal{J}_{3}.

Note that 𝒥3subscript𝒥3\mathcal{J}_{3} is in a sense the family with the smallest 𝒥3(1¯)subscript𝒥3¯1\mathcal{J}_{3}(\bar{1}) among the ones that satisfy the condition of the theorem. Before we prove it, let us put it into context. The following theorem is one of the main results in [20]:

Theorem 14 ([20]).

Let k5𝑘5k\geq 5 and n=n(k)𝑛𝑛𝑘n=n(k) be sufficiently large. If ([n]k)binomialdelimited-[]𝑛𝑘\mathcal{F}\subset{[n]\choose k} is intersecting, and ||>|𝒥3|subscript𝒥3|\mathcal{F}|>|\mathcal{J}_{3}|, then lsubscript𝑙\mathcal{F}\subset\mathcal{F}_{l} for l{0,k1,nk}𝑙0𝑘1𝑛𝑘l\in\{0,\ldots k-1,n-k\}.

Many results in extremal set theory are much easier to get once one assumes that n𝑛n is sufficiently large in comparison to k𝑘k. In this paper we prove the theorem above without the restriction on n𝑛n. It follows immediately from Theorem 13.

Theorem 15.

Let k5𝑘5k\geq 5 and n>2k𝑛2𝑘n>2k. If ([n]k)binomialdelimited-[]𝑛𝑘\mathcal{F}\subset{[n]\choose k} is intersecting, and |||𝒥3|subscript𝒥3|\mathcal{F}|\geq|\mathcal{J}_{3}|, then either \mathcal{F} is isomorphic to 𝒥3subscript𝒥3\mathcal{J}_{3}, or to a subset of lsubscript𝑙\mathcal{F}_{l} for l{0,k1,nk}𝑙0𝑘1𝑛𝑘l\in\{0,\ldots k-1,n-k\}.

We note that |𝒥3|<|nk|subscript𝒥3subscript𝑛𝑘|\mathcal{J}_{3}|<|\mathcal{F}_{n-k}| for n=ck𝑛𝑐𝑘n=ck: e.g., taking n>4k𝑛4𝑘n>4k is sufficient.

The following theorem is one of the main results of this paper. It generalizes Theorem 13 and gives a reasonable classification of all large intersecting families (actually, all families with not too large diversity). We prove it using yet another variation of our methods. Let us call a family 𝒢([2,n]k)𝒢binomial2𝑛𝑘\mathcal{G}\subset{[2,n]\choose k} typical minimal, if, first, for any Gl𝒢subscript𝐺𝑙𝒢G_{l}\in\mathcal{G} we have |G𝒢{Gl}G|>|G𝒢G|subscript𝐺𝒢subscript𝐺𝑙𝐺subscript𝐺𝒢𝐺|\cap_{G\in\mathcal{G}\setminus\{G_{l}\}}G|>|\cap_{G\in\mathcal{G}}G|, and, second, either |𝒢|=2𝒢2|\mathcal{G}|=2 or the number of elements contained in at least 222 sets from 𝒢𝒢\mathcal{G} is strictly bigger than |𝒢|𝒢|\mathcal{G}|. (Note that the first condition implies that there are at least |𝒢|𝒢|\mathcal{G}| elements contained in exactly |𝒢|1𝒢1|\mathcal{G}|-1 sets from 𝒢𝒢\mathcal{G}. Therefore, the second condition is, in particular, satisfied when |G𝒢G|>0subscript𝐺𝒢𝐺0|\cap_{G\in\mathcal{G}}G|>0.)

Theorem 16.

Assume that n>2k8𝑛2𝑘8n>2k\geq 8. Consider an intersecting family ([n]k)binomialdelimited-[]𝑛𝑘\mathcal{F}\subset{[n]\choose k}, such that Δ()=δ(1)Δ𝛿1\Delta(\mathcal{F})=\delta(1). Assume that |F(1¯)F|=rsubscript𝐹¯1𝐹𝑟|\cap_{F\in\mathcal{F}(\bar{1})}F|=r, where r[0,k1]𝑟0𝑘1r\in[0,k-1]. Choose any k1tr𝑘1𝑡𝑟k-1\geq t\geq r and any typical minimal subfamily 𝒢(1¯)𝒢¯1\mathcal{G}\subset\mathcal{F}(\bar{1}), such that |F𝒢F|=tsubscript𝐹𝒢𝐹𝑡|\cap_{F\in\mathcal{G}}F|=t. Take the (unique) maximal intersecting family superscript\mathcal{F}^{\prime}, such that (1¯)=𝒢superscript¯1𝒢\mathcal{F}^{\prime}(\bar{1})=\mathcal{G}. Then, if t4𝑡4t\geq 4 or γ()(n5k4)𝛾binomial𝑛5𝑘4\gamma(\mathcal{F})\leq{n-5\choose k-4}, we have

||||,superscript|\mathcal{F}|\leq|\mathcal{F}^{\prime}|, (14)

and equality is possible if and only if t=r𝑡𝑟t=r and \mathcal{F} is isomorphic to superscript\mathcal{F}^{\prime}. In particular, in conditions above, if there are two sets in A,B(1¯)𝐴𝐵¯1A,B\in\mathcal{F}(\bar{1}), such that |AB|=ks+1𝐴𝐵𝑘𝑠1|A\cap B|=k-s+1 for some s=2,,k𝑠2𝑘s=2,\ldots,k, then

|||𝒥s|subscript𝒥𝑠|\mathcal{F}|\leq|\mathcal{J}_{s}| (15)

with the equality only possible if \mathcal{F} is isomorphic to 𝒥ssubscript𝒥𝑠\mathcal{J}_{s}.

We note that r3𝑟3r\geq 3 implies both t3𝑡3t\geq 3 and γ()>(n5k4)𝛾binomial𝑛5𝑘4\gamma(\mathcal{F})>{n-5\choose k-4}, which, in turn, implies ||(n1k1)(n5k1)+(n5k4)binomial𝑛1𝑘1binomial𝑛5𝑘1binomial𝑛5𝑘4|\mathcal{F}|\leq{n-1\choose k-1}-{n-5\choose k-1}+{n-5\choose k-4} due to Theorem 2. Therefore, in particular, all families of size bigger than that are covered by the theorem.

4.1 Proof of Theorem 13

We are not going to use Theorem 7, but rather give a self-contained proof in the spirit of the proofs in [24]. The proof is rather simple and consists of two important steps. The first is, via shifting and rearranging the elements, to reduce the family in question to a family that has certain structure (that is, sets of particular form). The second step is to use the method in the spirit of Lemmas 1, 2.

Let us first give the definitions related to shifting.

For a given pair of indices 1i<jn1𝑖𝑗𝑛1\leq i<j\leq n and a set A[n]𝐴delimited-[]𝑛A\subset[n] define its (i,j)𝑖𝑗(i,j)-shift Si,j(A)subscript𝑆𝑖𝑗𝐴S_{i,j}(A) as follows. If iA𝑖𝐴i\in A or jA𝑗𝐴j\notin A, then Si,j(A)=Asubscript𝑆𝑖𝑗𝐴𝐴S_{i,j}(A)=A. If jA,iAformulae-sequence𝑗𝐴𝑖𝐴j\in A,i\notin A, then Si,j(A):=(A{j}){i}assignsubscript𝑆𝑖𝑗𝐴𝐴𝑗𝑖S_{i,j}(A):=(A-\{j\})\cup\{i\}. That is, Si,j(A)subscript𝑆𝑖𝑗𝐴S_{i,j}(A) is obtained from A𝐴A by replacing j𝑗j with i𝑖i.

The (i,j)𝑖𝑗(i,j)-shift Si,j()subscript𝑆𝑖𝑗S_{i,j}(\mathcal{F}) of a family \mathcal{F} is as follows:

Si,j():={Si,j(A):A}{A:A,Si,j(A)}.assignsubscript𝑆𝑖𝑗conditional-setsubscript𝑆𝑖𝑗𝐴𝐴conditional-set𝐴𝐴subscript𝑆𝑖𝑗𝐴S_{i,j}(\mathcal{F}):=\{S_{i,j}(A):A\in\mathcal{F}\}\cup\{A:A,S_{i,j}(A)\in\mathcal{F}\}.

We call a family \mathcal{F} shifted, if Si,j()=subscript𝑆𝑖𝑗S_{i,j}(\mathcal{F})=\mathcal{F} for all 1i<jn1𝑖𝑗𝑛1\leq i<j\leq n.

We note that shifts do not destroy the cross-intersecting property, therefore, any pair of cross-intersecting families may be transformed into a pair of shifted cross-intersecting families.

Take the family \mathcal{F} satisfying the requirements of the statement. If γ()=2𝛾2\gamma(\mathcal{F})=2, then \mathcal{F} is isomorphic to one of the 𝒥isubscript𝒥𝑖\mathcal{J}_{i}, i=3,,k+1𝑖3𝑘1i=3,\ldots,k+1, and we know that 𝒥3subscript𝒥3\mathcal{J}_{3} is the largest out of them. Therefore, we may assume that γ()3𝛾3\gamma(\mathcal{F})\geq 3.

Consider the families 𝒜:=(1),:=(1¯)formulae-sequenceassign𝒜1assign¯1{\mathcal{A}}:=\mathcal{F}(1),\ {\mathcal{B}}:=\mathcal{F}(\bar{1}). They are cross-intersecting. There are two cases to consider.

Case 1. Assume that we have two sets A,B(1¯)𝐴𝐵¯1A,B\in\mathcal{F}(\bar{1}), such that |AB|k2𝐴𝐵𝑘2|A\cap B|\leq k-2.

First of all, by doing shifts, we may assume that there are two sets B1,B2subscript𝐵1subscript𝐵2B_{1},B_{2}\in{\mathcal{B}}, such that |B1B2|=k2subscript𝐵1subscript𝐵2𝑘2|B_{1}\cap B_{2}|=k-2. W.l.o.g., we may assume that B1=[2,k1]{k+1,k+2}subscript𝐵12𝑘1𝑘1𝑘2B_{1}=[2,k-1]\cup\{k+1,k+2\}, and that B2=[2,k]{k+3}subscript𝐵22𝑘𝑘3B_{2}=[2,k]\cup\{k+3\}.

We have at least one more set B3subscript𝐵3B_{3} in {\mathcal{B}}. Doing (i,j)𝑖𝑗(i,j)-shifts, where i[2,k1]𝑖2𝑘1i\in[2,k-1] and j[k,n]𝑗𝑘𝑛j\in[k,n], we can assume that B3[2,k1]2𝑘1subscript𝐵3B_{3}\supset[2,k-1]. Apart from these elements, there are two more elements in B3subscript𝐵3B_{3}, say, j1subscript𝑗1j_{1} and j2subscript𝑗2j_{2}, j1<j2subscript𝑗1subscript𝑗2j_{1}<j_{2}. Either j1=ksubscript𝑗1𝑘j_{1}=k, or j2k+3subscript𝑗2𝑘3j_{2}\geq k+3, and we can do a (k,j2)𝑘subscript𝑗2(k,j_{2})-shift (or a (k,j1)𝑘subscript𝑗1(k,j_{1})-shift, if j1=k+3subscript𝑗1𝑘3j_{1}=k+3), thus assuring that [2,k]B32𝑘subscript𝐵3[2,k]\in B_{3}. Denote by j𝑗j the only remaining element of B3subscript𝐵3B_{3}. Clearly, jk+3𝑗𝑘3j\neq k+3, since otherwise B3=B2subscript𝐵3subscript𝐵2B_{3}=B_{2}, and therefore we can safely do a (k+1,j)𝑘1𝑗(k+1,j)-shift, thus transforming B3subscript𝐵3B_{3} into [2,k+1]2𝑘1[2,k+1] and not changing B1,B2subscript𝐵1subscript𝐵2B_{1},\ B_{2}. Moreover, if γ()4𝛾4\gamma(\mathcal{F})\geq 4, then there is yet another set B4subscript𝐵4B_{4}, which, in a similar way, we can transform into [2,k]{k+2}2𝑘𝑘2[2,k]\cup\{k+2\}. In what follows, we assume that B3=[2,k+1]subscript𝐵32𝑘1B_{3}=[2,k+1] and B4=[2,k]{k+2}.subscript𝐵42𝑘𝑘2B_{4}=[2,k]\cup\{k+2\}.

Assume first that γ()=||=3𝛾3\gamma(\mathcal{F})=|{\mathcal{B}}|=3 and ={B1,B2,B3}subscript𝐵1subscript𝐵2subscript𝐵3{\mathcal{B}}=\{B_{1},B_{2},B_{3}\} as above. Then we can use the following simple argument. Remove the set B3subscript𝐵3B_{3} from {\mathcal{B}}, thus decreasing the sum of cardinalities of 𝒜𝒜{\mathcal{A}} and {\mathcal{B}} by 111, and then add to 𝒜𝒜{\mathcal{A}} all the (k1)𝑘1(k-1)-sets from the family

𝒜1:={A([2,n]k1):A[k+1]=,{k+2,k+3}A}.assignsubscript𝒜1conditional-set𝐴binomial2𝑛𝑘1formulae-sequence𝐴delimited-[]𝑘1𝑘2𝑘3𝐴{\mathcal{A}}_{1}:=\big{\{}A\in{[2,n]\choose k-1}:A\cap[k+1]=\emptyset,\{k+2,k+3\}\in A\big{\}}. (16)

Clearly, each set from 𝒜1subscript𝒜1{\mathcal{A}}_{1} will intersect both B1subscript𝐵1B_{1} and B2subscript𝐵2B_{2}, and thus the pair 𝒜,𝒜{\mathcal{A}},{\mathcal{B}} will remain cross-intersecting. However, none of the sets from 𝒜1subscript𝒜1{\mathcal{A}}_{1} was present in 𝒜𝒜{\mathcal{A}} before, since each set from 𝒜1subscript𝒜1{\mathcal{A}}_{1} is disjoint with B3subscript𝐵3B_{3}. Therefore, we increase the sum of cardinalities of 𝒜𝒜{\mathcal{A}} and {\mathcal{B}} by |𝒜1|=(nk3k3)subscript𝒜1binomial𝑛𝑘3𝑘3|{\mathcal{A}}_{1}|={n-k-3\choose k-3}, which is more than 111 for n>2k𝑛2𝑘n>2k, k4𝑘4k\geq 4. Therefore, the resulting cross-intersecting pair, which corresponds to the family 𝒥3subscript𝒥3\mathcal{J}_{3}, is bigger than the initial one.

If γ()=||4𝛾4\gamma(\mathcal{F})=|{\mathcal{B}}|\geq 4, then, due to the discussion two paragraphs above, we may assume that Bisubscript𝐵𝑖B_{i}\in{\mathcal{B}}, i[4]𝑖delimited-[]4i\in[4], and that 𝒜,𝒜{\mathcal{A}},{\mathcal{B}} are shifted. Let T𝑇T be the lexicographically last element in {\mathcal{B}}. since the family {\mathcal{B}} is itself intersecting, for each set B𝐵B\in{\mathcal{B}} there must be an i𝑖i such that

|[2,i]B|>|[2,i]B|,2𝑖𝐵2𝑖𝐵|[2,i]\cap B|>|[2,i]\setminus B|, (17)

because otherwise one of the sets in [2,n]2𝑛[2,n] that may be obtained from B𝐵B by shifts will be disjoint from B𝐵B, but at the same time it will lie in {\mathcal{B}}.

Let us find the biggest such i𝑖i for T𝑇T and consider a bipartite graph G𝐺G with parts

𝒫a:=assignsubscript𝒫𝑎absent\displaystyle\mathcal{P}_{a}:= {P([2,n]k1):P[i]=[2,i]B},conditional-set𝑃binomial2𝑛𝑘1𝑃delimited-[]𝑖2𝑖𝐵\displaystyle\big{\{}P\in{[2,n]\choose k-1}:P\cap[i]=[2,i]\setminus B\big{\}},
𝒫b:=assignsubscript𝒫𝑏absent\displaystyle\mathcal{P}_{b}:= {P([2,n]k):P[i]=[2,i]B}conditional-set𝑃binomial2𝑛𝑘𝑃delimited-[]𝑖2𝑖𝐵\displaystyle\big{\{}P\in{[2,n]\choose k}:P\cap[i]=[2,i]\cap B\big{\}}

and edges connecting disjoint sets. Then we see that, due to (17) and n1>2k1𝑛12𝑘1n-1>2k-1, |𝒫a||𝒫b|subscript𝒫𝑎subscript𝒫𝑏|\mathcal{P}_{a}|\geq|\mathcal{P}_{b}|. At the same time, (𝒜𝒫a)(𝒫b)𝒜subscript𝒫𝑎subscript𝒫𝑏({\mathcal{A}}\cap\mathcal{P}_{a})\cup({\mathcal{B}}\cap\mathcal{P}_{b}) is an independent set in G𝐺G and thus has size at most |𝒫a|subscript𝒫𝑎|\mathcal{P}_{a}|. Therefore, replacing 𝒜,𝒜{\mathcal{A}},\ {\mathcal{B}} with 𝒜:=𝒜𝒫aassignsuperscript𝒜𝒜subscript𝒫𝑎{\mathcal{A}}^{\prime}:={\mathcal{A}}\cup\mathcal{P}_{a}, :=𝒫bassignsuperscriptsubscript𝒫𝑏{\mathcal{B}}^{\prime}:={\mathcal{B}}\setminus\mathcal{P}_{b}, we do not decrease the sum of sizes. Moreover, it is easy to see that superscript{\mathcal{B}}^{\prime} is intersecting (since superscript{\mathcal{B}}^{\prime}\subset{\mathcal{B}}) and that 𝒜,superscript𝒜superscript{\mathcal{A}}^{\prime},{\mathcal{B}}^{\prime} are cross-intersecting. Indeed, any set in superscript{\mathcal{B}}^{\prime} must intersect [2,i]2𝑖[2,i] in a set which lexicographically precedes [2,i]B2𝑖𝐵[2,i]\cap B, and thus which intersects [2,i]B2𝑖𝐵[2,i]\setminus B. Moreover, the family superscript{\mathcal{B}}^{\prime} is shifted.

We repeat this with the lexicographically last element in superscript{\mathcal{B}}^{\prime}, etc., until the lexicographically last set of the second family is B1subscript𝐵1B_{1}. We note that we will arrive at such a moment. Indeed, the only obstacle is that we somehow remove B1subscript𝐵1B_{1} from the second family due to the fact that B1𝒫bsubscript𝐵1subscript𝒫𝑏B_{1}\in\mathcal{P}_{b}, where 𝒫bsubscript𝒫𝑏\mathcal{P}_{b} was defined by some other set Bsuperscript𝐵B^{\prime} in the second family. Let us show that this is impossible. Recall that we chose i𝑖i as the largest index, for which the inequality (17) is satisfied. We must have B[2,i]=B1[2,i]superscript𝐵2𝑖subscript𝐵12𝑖B^{\prime}\cap[2,i]=B_{1}\cap[2,i]. On the other hand, by the maximality of i𝑖i, we have 1=|B[2,i]||B[2,i]|=|B[2,i]||B[2,i]|1superscript𝐵2𝑖superscript𝐵2𝑖𝐵2𝑖𝐵2𝑖1=|B^{\prime}\cap[2,i]|-|B^{\prime}\setminus[2,i]|=|B\cap[2,i]|-|B\setminus[2,i]|. But |B[2,i]||B[2,i]|2𝐵2𝑖𝐵2𝑖2|B\cap[2,i]|-|B\setminus[2,i]|\geq 2 for any ik+2𝑖𝑘2i\leq k+2.

Therefore, we may assume that B1subscript𝐵1B_{1} is the lexicographically last element in {\mathcal{B}}. Thus, each B,𝐵B\in{\mathcal{B}}, BB1𝐵subscript𝐵1B\neq B_{1}, satisfies [2,k]B2𝑘𝐵[2,k]\subset B. The number of such sets is nk𝑛𝑘n-k, and this, in particular, implies that ||nk+1𝑛𝑘1|{\mathcal{B}}|\leq n-k+1. At the same time, Bisubscript𝐵𝑖B_{i}\in{\mathcal{B}}, i=[4]𝑖delimited-[]4i=[4], since they all precede B1subscript𝐵1B_{1} lexicographically (and thus could not have been removed before B1subscript𝐵1B_{1}).

Removing all the sets from {\mathcal{B}} apart from B1,B2subscript𝐵1subscript𝐵2B_{1},B_{2} will decrease |𝒜|+||𝒜|{\mathcal{A}}|+|{\mathcal{B}}| by at most nk1𝑛𝑘1n-k-1. At the same time, we may add to 𝒜𝒜{\mathcal{A}} the family 𝒜1subscript𝒜1{\mathcal{A}}_{1} as well as the following family:

𝒜2:={A([2,n]k1):A([k]{k+2})=,{k+1,k+3}A}.assignsubscript𝒜2conditional-set𝐴binomial2𝑛𝑘1formulae-sequence𝐴delimited-[]𝑘𝑘2𝑘1𝑘3𝐴{\mathcal{A}}_{2}:=\big{\{}A\in{[2,n]\choose k-1}:A\cap([k]\cup\{k+2\})=\emptyset,\{k+1,k+3\}\in A\big{\}}. (18)

We have |𝒜1|=|𝒜2|=(nk3k3)nk3subscript𝒜1subscript𝒜2binomial𝑛𝑘3𝑘3𝑛𝑘3|{\mathcal{A}}_{1}|=|{\mathcal{A}}_{2}|={n-k-3\choose k-3}\geq n-k-3, and both 𝒜1subscript𝒜1{\mathcal{A}}_{1} and 𝒜2subscript𝒜2{\mathcal{A}}_{2} are disjoint with 𝒜𝒜{\mathcal{A}}, since B3,B4subscript𝐵3subscript𝐵4B_{3},B_{4}\in{\mathcal{B}}. Thus we are getting 2(nk3)2𝑛𝑘32(n-k-3) new sets, and 2(nk3)(nk1)=nk5>02𝑛𝑘3𝑛𝑘1𝑛𝑘502(n-k-3)-(n-k-1)=n-k-5>0 for n>2k,k5formulae-sequence𝑛2𝑘𝑘5n>2k,k\geq 5. Therefore, we conclude that in this case as well, the size of the family \mathcal{F} is smaller than the size of 𝒥2subscript𝒥2\mathcal{J}_{2}.

Case 2. Assume that any two sets in (1¯)¯1\mathcal{F}(\bar{1}) intersect in at least k1𝑘1k-1 elements. Then, knowing that |F(1¯)F|k2subscript𝐹¯1𝐹𝑘2|\cap_{F\in\mathcal{F}(\bar{1})}F|\leq k-2, we may assume that (1¯)([2,k+2]k)¯1binomial2𝑘2𝑘\mathcal{F}(\bar{1})\subset{[2,k+2]\choose k} (indeed, it is easy to check that all sets in (1¯)¯1\mathcal{F}(\bar{1}) must be contained in a certain k+1𝑘1k+1-set). We may w.l.o.g. assume that the sets C1=[2,k+1],C2=[2,k]{k+2},C3=[2,k1]{k+1,k+2}formulae-sequencesubscript𝐶12𝑘1formulae-sequencesubscript𝐶22𝑘𝑘2subscript𝐶32𝑘1𝑘1𝑘2C_{1}=[2,k+1],\ C_{2}=[2,k]\cup\{k+2\},\ C_{3}=[2,k-1]\cup\{k+1,k+2\} are contained in (1¯)¯1\mathcal{F}(\bar{1}). Let us look at the sets that Cisubscript𝐶𝑖C_{i} forbid in (1)1\mathcal{F}(1), as compared to the sets that are forbidden by B1,B2subscript𝐵1subscript𝐵2B_{1},B_{2}. In both cases (1)1\mathcal{F}(1) contain all sets intersecting [k1]delimited-[]𝑘1[k-1], as well sets containing {k}𝑘\{k\} and one of {k+1,k+2}𝑘1𝑘2\{k+1,k+2\}. Apart from the one listed above, the sets Cisubscript𝐶𝑖C_{i} allow only for sets that intersect [k+2]delimited-[]𝑘2[k+2] in {k+1,k+2}𝑘1𝑘2\{k+1,k+2\} (their number is (nk2k3)binomial𝑛𝑘2𝑘3{n-k-2\choose k-3}), while the sets Bisubscript𝐵𝑖B_{i} allow for the sets that contain {k+3}𝑘3\{k+3\}, disjoint with [k]delimited-[]𝑘[k], and intersect [k+1,k+2]𝑘1𝑘2[k+1,k+2] in at least one element (their number is (nk2k3)+(nk3k3)binomial𝑛𝑘2𝑘3binomial𝑛𝑘3𝑘3{n-k-2\choose k-3}+{n-k-3\choose k-3}). Therefore, we can have (nk3k3)binomial𝑛𝑘3𝑘3{n-k-3\choose k-3} sets more with B1,B2subscript𝐵1subscript𝐵2B_{1},\ B_{2} than with C1,C2,C3subscript𝐶1subscript𝐶2subscript𝐶3C_{1},C_{2},C_{3}. On the other hand, in this case |(1¯)|2k1<(nk3k3)¯12𝑘1binomial𝑛𝑘3𝑘3|\mathcal{F}(\bar{1})|-2\leq k-1<{n-k-3\choose k-3} for any n>2k10𝑛2𝑘10n>2k\geq 10. So we conclude that the families in this case are also smaller than 𝒥2subscript𝒥2\mathcal{J}_{2}.

4.2 Proof of Theorem 16

Choose \mathcal{F}, t𝑡t, 𝒢𝒢\mathcal{G}, and superscript\mathcal{F}^{\prime} satisfying the requirements of the theorem. We aim to prove that any family \mathcal{F} satisfying the requirements of the theorem has size strictly smaller than superscript\mathcal{F}^{\prime}, unless it is isomorphic to superscript\mathcal{F}^{\prime}. As a condition, in some of the cases we have γ()(n5k4)𝛾binomial𝑛5𝑘4\gamma(\mathcal{F})\leq{n-5\choose k-4}. If it does not hold, but we have t4𝑡4t\geq 4 instead, then we still may assume that γ()(n5k4)𝛾binomial𝑛5𝑘4\gamma(\mathcal{F})\leq{n-5\choose k-4}. Indeed, the largest family with diversity >(n5k4)absentbinomial𝑛5𝑘4>{n-5\choose k-4} is at most as large as missingH5:={A([n]k):[2,5]A}{A([n]k):1A,[2,5]A}assignmissingsubscript𝐻5conditional-set𝐴binomialdelimited-[]𝑛𝑘25𝐴conditional-set𝐴binomialdelimited-[]𝑛𝑘formulae-sequence1𝐴25𝐴\mathcal{\mathcal{missing}}H_{5}:=\{A\in{[n]\choose k}:[2,5]\subset A\}\cup\{A\in{[n]\choose k}:1\in A,[2,5]\cap A\neq\emptyset\}, and the latter family satisfies the requirements of the theorem (it contains a copy of any 𝒢𝒢\mathcal{G} as in the statement). Therefore, if we show that superscript\mathcal{F}^{\prime} is bigger than 5subscript5\mathcal{H}_{5}, it implies that superscript\mathcal{F}^{\prime} is bigger than any family with diversity >(n5k4)absentbinomial𝑛5𝑘4>{n-5\choose k-4}.

Therefore, from now on we assume that γ()(n5k4)𝛾binomial𝑛5𝑘4\gamma(\mathcal{F})\leq{n-5\choose k-4}. Assume that F𝒢F=[2,t+1]subscript𝐹𝒢𝐹2𝑡1\cap_{F\in\mathcal{G}}F=[2,t+1] (note that it may be empty). For each i[2,t+1]𝑖2𝑡1i\in[2,t+1] consider the following bipartite graph. The parts are

𝒫a:=assignsubscript𝒫𝑎absent\displaystyle\mathcal{P}_{a}:= {P{i}:P(1),iP},conditional-set𝑃𝑖formulae-sequence𝑃1𝑖𝑃\displaystyle\big{\{}P\setminus\{i\}:P\in\mathcal{F}(1),i\in P\},
𝒫b:=assignsubscript𝒫𝑏absent\displaystyle\mathcal{P}_{b}:= {P(1¯):iP},conditional-set𝑃¯1𝑖𝑃\displaystyle\big{\{}P\in\mathcal{F}(\bar{1}):i\notin P\big{\}},

and edges connect disjoint sets. Note that 𝒫a(Xk2)subscript𝒫𝑎binomial𝑋𝑘2\mathcal{P}_{a}\subset{X\choose k-2}, 𝒫b(Xk)subscript𝒫𝑏binomial𝑋𝑘\mathcal{P}_{b}\subset{X\choose k}, where X=[2,n]{i}𝑋2𝑛𝑖X=[2,n]\setminus\{i\}, |X|=n2>k+k2𝑋𝑛2𝑘𝑘2|X|=n-2>k+k-2. Due to the condition on γ()𝛾\gamma(\mathcal{F}), we have |𝒫b(1¯)|(n5k4)<(|X|3(k2)1)subscript𝒫𝑏¯1binomial𝑛5𝑘4binomial𝑋3𝑘21|\mathcal{P}_{b}\cap\mathcal{F}(\bar{1})|\leq{n-5\choose k-4}<{|X|-3\choose(k-2)-1}. Thus, we can apply (10) to

𝒜:=assign𝒜absent\displaystyle{\mathcal{A}}:= (1)𝒫aand1subscript𝒫𝑎and\displaystyle\mathcal{F}(1)\cap\mathcal{P}_{a}\ \ \ \ \text{and}
:=assignabsent\displaystyle{\mathcal{B}}:= (1¯)𝒫b,¯1subscript𝒫𝑏\displaystyle\mathcal{F}(\bar{1})\cap\mathcal{P}_{b},

and conclude that |𝒜|+||(|X|k2)𝒜binomial𝑋𝑘2|{\mathcal{A}}|+|{\mathcal{B}}|\leq{|X|\choose k-2}. Therefore, removing (1¯)𝒫b¯1subscript𝒫𝑏\mathcal{F}(\bar{1})\cap\mathcal{P}_{b} from (1¯)¯1\mathcal{F}(\bar{1}) and adding sets from 𝒫asubscript𝒫𝑎\mathcal{P}_{a} to (1)1\mathcal{F}(1), we get a pair of families with larger sum of cardinalities. Moreover, the new pair is cross-intersecting: all sets in (1¯)𝒫b¯1subscript𝒫𝑏\mathcal{F}(\bar{1})\setminus\mathcal{P}_{b} contain i𝑖i, as well as the sets from 𝒫asubscript𝒫𝑎\mathcal{P}_{a}. Therefore, we may assume that all sets in (1¯)¯1\mathcal{F}(\bar{1}) contain [2,t+1]2𝑡1[2,t+1].

Put 𝒢={G1,,Gz}𝒢subscript𝐺1subscript𝐺𝑧\mathcal{G}=\{G_{1},\ldots,G_{z}\}. Due to minimality of 𝒢𝒢\mathcal{G}, for each Gl𝒢subscript𝐺𝑙𝒢G_{l}\in\mathcal{G}, l[z]𝑙delimited-[]𝑧l\in[z], there is

il(G𝒢{Gl}G)(G𝒢G).subscript𝑖𝑙subscript𝐺𝒢subscript𝐺𝑙𝐺subscript𝐺𝒢𝐺i_{l}\in\Big{(}\bigcap_{G\in\mathcal{G}\setminus\{G_{l}\}}G\Big{)}\setminus\Big{(}\bigcap_{G\in\mathcal{G}}G\Big{)}.

We assume that il=t+l+1subscript𝑖𝑙𝑡𝑙1i_{l}=t+l+1, l[z]𝑙delimited-[]𝑧l\in[z]. In particular, {i1,,iz}=[t+2,t+z+1]subscript𝑖1subscript𝑖𝑧𝑡2𝑡𝑧1\{i_{1},\ldots,i_{z}\}=[t+2,t+z+1].

Next, for each set i[t+2,t+z+1]𝑖𝑡2𝑡𝑧1i\in[t+2,t+z+1] consider the same bipartite graph as before. We can apply (11) with j:=kassign𝑗𝑘j:=k. Indeed, we know that ||(|X|kk)=1binomial𝑋𝑘𝑘1|{\mathcal{B}}|\geq{|X|\choose k-k}=1 since Git1𝒫bsubscript𝐺𝑖𝑡1subscript𝒫𝑏G_{i-t-1}\in\mathcal{P}_{b} (note that Gl𝒫bsubscript𝐺𝑙subscript𝒫𝑏G_{l}\notin\mathcal{P}_{b} for lit1𝑙𝑖𝑡1l\neq i-t-1, since all of them contain ilsubscript𝑖𝑙i_{l} due to the definition of ilsubscript𝑖𝑙i_{l}). Therefore, |𝒜|+||(n2k2)(nk2k2)+1𝒜binomial𝑛2𝑘2binomial𝑛𝑘2𝑘21|\mathcal{A}|+|\mathcal{B}|\leq{n-2\choose k-2}-{n-k-2\choose k-2}+1, and we may replace 𝒜,𝒜{\mathcal{A}},\ {\mathcal{B}} with :={B}assignsuperscript𝐵{\mathcal{B}}^{\prime}:=\{B\} and 𝒜:={A(Xk2):AB}assignsuperscript𝒜conditional-set𝐴binomial𝑋𝑘2𝐴𝐵{\mathcal{A}}^{\prime}:=\{A\in{X\choose k-2}:A\cap B\neq\emptyset\}. The resulting family is cross-intersecting. Repeating this procedure, we may conclude that any set in (1¯)¯1\mathcal{F}(\bar{1}) not from 𝒢𝒢\mathcal{G} must contain the set [2,t+z+1]2𝑡𝑧1[2,t+z+1]. If there are any other elements contained in all but 1 set from 𝒢𝒢\mathcal{G}, we repeat the same procedure with them. Assume that they together with [2,t+z+1]2𝑡𝑧1[2,t+z+1] form a segment [2,t]2superscript𝑡[2,t^{\prime}]. Note that for each l[z]𝑙delimited-[]𝑧l\in[z] the set Gl[2,t]subscript𝐺𝑙2superscript𝑡G_{l}\cap[2,t^{\prime}] has the same size and must be non-empty. Otherwise, we have already proved the inequality (14), since the current (1¯)¯1\mathcal{F}(\bar{1}) is equal to 𝒢𝒢\mathcal{G}.

Recall that 𝒢𝒢\mathcal{G} is typical minimal, that is, the number of elements contained in at least 2 sets from 𝒢𝒢\mathcal{G} is at least z+1𝑧1z+1. If |[2,t]|z+12superscript𝑡𝑧1|[2,t^{\prime}]|\geq z+1 (which is the case, e.g., when t1𝑡1t\geq 1), then we proceed in the following way.

For each S[z]𝑆delimited-[]𝑧S\subset[z] of size z1𝑧1z-1 select one element ilGl[t+1,n]subscript𝑖𝑙subscript𝐺𝑙superscript𝑡1𝑛i_{l}\in G_{l}\cap[t^{\prime}+1,n] for each lS𝑙𝑆l\in S. Note that ilsubscript𝑖𝑙i_{l} may coincide. Put IS:={il:lS}assignsubscript𝐼𝑆conditional-setsubscript𝑖𝑙𝑙𝑆I_{S}:=\{i_{l}:l\in S\}. Consider a bipartite graph with parts

𝒫a:=assignsubscript𝒫𝑎absent\displaystyle\mathcal{P}_{a}:= {P:P(1),ISP,[2,t]P=},conditional-setlimit-from𝑃formulae-sequence𝑃1formulae-sequencesubscript𝐼𝑆𝑃2superscript𝑡𝑃\displaystyle\big{\{}P\setminus:P\in\mathcal{F}(1),I_{S}\subset P,[2,t^{\prime}]\cap P=\emptyset\},
𝒫b:=assignsubscript𝒫𝑏absent\displaystyle\mathcal{P}_{b}:= {P[2,t]:P(1¯),ISP=,[2,t]P},conditional-set𝑃2superscript𝑡formulae-sequence𝑃¯1formulae-sequencesubscript𝐼𝑆𝑃2superscript𝑡𝑃\displaystyle\big{\{}P\setminus[2,t^{\prime}]:P\in\mathcal{F}(\bar{1}),I_{S}\cap P=\emptyset,[2,t^{\prime}]\subset P\big{\}},

and edges connecting disjoint sets. Note that 𝒫a(Ykz)subscript𝒫𝑎binomial𝑌𝑘superscript𝑧\mathcal{P}_{a}\subset{Y\choose k-z^{\prime}}, zzsuperscript𝑧𝑧z^{\prime}\leq z, and 𝒫b(Ykz′′)subscript𝒫𝑏binomial𝑌𝑘superscript𝑧′′\mathcal{P}_{b}\subset{Y\choose k-z^{\prime\prime}}, z′′z+1superscript𝑧′′𝑧1z^{\prime\prime}\geq z+1, where Y=[t+1,n]IS𝑌superscript𝑡1𝑛subscript𝐼𝑆Y=[t^{\prime}+1,n]\setminus I_{S}, |Y|=nz′′z𝑌𝑛superscript𝑧′′superscript𝑧|Y|=n-z^{\prime\prime}-z^{\prime}. In particular, |Y|>kz+kz′′𝑌𝑘superscript𝑧𝑘superscript𝑧′′|Y|>k-z^{\prime}+k-z^{\prime\prime}. We have |𝒢𝒫b|{0,1}𝒢subscript𝒫𝑏01|\mathcal{G}\cap\mathcal{P}_{b}|\in\{0,1\}. Indeed, only the set Gl,{l}=[z]Ssubscript𝐺𝑙𝑙delimited-[]𝑧𝑆G_{l},\ \{l\}=[z]\setminus S may be left. Denote

𝒜:=assign𝒜absent\displaystyle{\mathcal{A}}:= (1)𝒫aand1subscript𝒫𝑎and\displaystyle\mathcal{F}(1)\cap\mathcal{P}_{a}\ \ \ \ \text{and}
:=assignabsent\displaystyle{\mathcal{B}}:= (1¯)𝒫b.¯1subscript𝒫𝑏\displaystyle\mathcal{F}(\bar{1})\cap\mathcal{P}_{b}.

We have kz>kz′′𝑘superscript𝑧𝑘superscript𝑧′′k-z^{\prime}>k-z^{\prime\prime}, and, therefore, we may apply either (10) or (11) with a:=kz,b:=kz′′,j:=kz′′formulae-sequenceassign𝑎𝑘superscript𝑧formulae-sequenceassign𝑏𝑘superscript𝑧′′assign𝑗𝑘superscript𝑧′′a:=k-z^{\prime},\ b:=k-z^{\prime\prime},\ j:=k-z^{\prime\prime} (the upper bound on |||{\mathcal{B}}| becomes trivial in that case) and conclude that either |𝒜|+||(|Y|kz)𝒜binomial𝑌𝑘superscript𝑧|{\mathcal{A}}|+|{\mathcal{B}}|\leq{|Y|\choose k-z^{\prime}} or |𝒜|+||(|Y|kz)(|Y|k+z′′kz)+1𝒜binomial𝑌𝑘superscript𝑧binomial𝑌𝑘superscript𝑧′′𝑘superscript𝑧1|{\mathcal{A}}|+|{\mathcal{B}}|\leq{|Y|\choose k-z^{\prime}}-{|Y|-k+z^{\prime\prime}\choose k-z^{\prime}}+1. In both cases we may replace {\mathcal{B}} with 𝒫b𝒢subscript𝒫𝑏𝒢\mathcal{P}_{b}\cap\mathcal{G} and 𝒜𝒜{\mathcal{A}} with all sets from 𝒫asubscript𝒫𝑎\mathcal{P}_{a} that intersect the set from 𝒫b𝒢subscript𝒫𝑏𝒢\mathcal{P}_{b}\cap\mathcal{G} (if it is non-empty). As before, the size does not decrease and the cross-intersecting property is preserved.

Repeating this for all possible choices of S𝑆S and ISsubscript𝐼𝑆I_{S}, we arrive at a point when any set from (1¯)𝒢¯1𝒢\mathcal{F}(\bar{1})\setminus\mathcal{G} must intersect any set ISsubscript𝐼𝑆I_{S}. Tt is clear that it only holds for a set F𝐹F if FGl[t+1,n]subscript𝐺𝑙superscript𝑡1𝑛𝐹F\supset G_{l}\cap[t^{\prime}+1,n]. But then F=Gl𝐹subscript𝐺𝑙F=G_{l}, so (1¯)=𝒢¯1𝒢\mathcal{F}(\bar{1})=\mathcal{G}, and the proof of (14) is complete in this case.

Assume now that |[2,t]|=z+12superscript𝑡𝑧1|[2,t^{\prime}]|=z+1. By the typical minimality of 𝒢𝒢\mathcal{G}, we have an element i𝑖absenti\in, which is contained in at least 2 sets, say, G1subscript𝐺1G_{1} and G2subscript𝐺2G_{2}. We do something very similar to the previous case, but we have to be a bit more careful. We select a z1𝑧1z-1-set S[z]𝑆delimited-[]𝑧S\subset[z], which includes 111 and 222, a set IS:={i}{il:l[3,z]S}assignsubscript𝐼𝑆𝑖conditional-setsubscript𝑖𝑙𝑙3𝑧𝑆I_{S}:=\{i\}\cup\{i_{l}:l\in[3,z]\cap S\}. It is clear that |IS|z2subscript𝐼𝑆𝑧2|I_{S}|\leq z-2. Next, we consider the same bipartite graph as before. The sets in part 𝒫asubscript𝒫𝑎\mathcal{P}_{a} now have size at least kz+1𝑘𝑧1k-z+1, while the sets in 𝒫bsubscript𝒫𝑏\mathcal{P}_{b} have size at most kz𝑘𝑧k-z. Therefore, we can apply (10), (11) in the same way, and arrive at a family (1¯)¯1\mathcal{F}(\bar{1}), such that any set in (1¯)𝒢¯1𝒢\mathcal{F}(\bar{1})\setminus\mathcal{G} intersects any set ISsubscript𝐼𝑆I_{S} of the form described above. In practice, this means that any set in (1¯)𝒢¯1𝒢\mathcal{F}(\bar{1})\setminus\mathcal{G} contains i𝑖i! Thus, we may now add i𝑖i to the set [2,t]2superscript𝑡[2,t^{\prime}] and proceed as in the first case: we now have at least z+1𝑧1z+1 common elements for all F(1¯)𝒢𝐹¯1𝒢F\in\mathcal{F}(\bar{1})\setminus\mathcal{G}. The inequality (14) is proven.

Finally, the uniqueness follows from the fact that the inequalities (10), (11) are strict unless the family {\mathcal{B}} has size 00 and 111, respectively. Therefore, if (1¯)𝒢¯1𝒢\mathcal{F}(\bar{1})\neq\mathcal{G}, then at some point we would have had a strict inequality in the application of (10), (11).

5 Degree versions

Recently, Huang and Zhao [17] gave an elegant proof of the following theorem using a linear-algebraic approach:

Theorem 17 ([17]).

Let n>2k>0𝑛2𝑘0n>2k>0. Then any intersecting family has minimum degree at most (n2k2)binomial𝑛2𝑘2{n-2\choose k-2}.

The bound in the theorem is tight because of the trivial intersecting family, and the condition n>2k𝑛2𝑘n>2k is necessary: in [17] the authors provide an example of a family for n=2k𝑛2𝑘n=2k which has larger minimal degree. In fact, for most values of k𝑘k there are regular intersecting families in ([2k]k)binomialdelimited-[]2𝑘𝑘{[2k]\choose k} of maximal possible size: (2k1k)binomial2𝑘1𝑘{2k-1\choose k} (see [18]). In the follow-up paper, Frankl, Han, Huang, and Zhao [8] proved

Theorem 18 ([8]).

Let k4𝑘4k\geq 4 and nck2𝑛𝑐superscript𝑘2n\geq ck^{2}, where c=30𝑐30c=30 for k=4,5𝑘45k=4,5, and c=4𝑐4c=4 for k6𝑘6k\geq 6. Then any non-trivial intersecting family has minimum degree at most (n2k2)(nk2k2)binomial𝑛2𝑘2binomial𝑛𝑘2𝑘2{n-2\choose k-2}-{n-k-2\choose k-2}.

Several questions and problems arose in this context, that were asked in [17], [8], as well as in personal communication with Hao Huang and his presentation on the Recent Advances in Extremal Combinatorics Workshop at TSIMF, Sanya. Some of them are as follows:

  1. 1.

    Can one find a combinatorial proof of Theorem 17? This question was partially answered by Frankl and Tokushige [13], who proved it under the additional assumption n3k𝑛3𝑘n\geq 3k. Huang claims that their proof can be made to work for n2k+3𝑛2𝑘3n\geq 2k+3, provided that one applies their approach more carefully. However, the cases n=2k+2𝑛2𝑘2n=2k+2 and n=2k+1𝑛2𝑘1n=2k+1 remained open.

  2. 2.

    Extend Theorem 18 to the case nck𝑛𝑐𝑘n\geq ck for large k𝑘k. Ultimately, prove Theorem 18 for all values n2k+1𝑛2𝑘1n\geq 2k+1 for which it is valid.

  3. 3.

    Extend Theorems 17 and 18 to degrees of t𝑡t-tuples of vertices. The degree of a subset S[n]𝑆delimited-[]𝑛S\subset[n] is the number of sets from the family containing S𝑆S. We denote by δt()subscript𝛿𝑡\delta_{t}(\mathcal{F}) the minimal degree of an t𝑡t-element subset S[n]𝑆delimited-[]𝑛S\subset[n].

In this section we address these questions, partially answering all three of them. In the first theorem, we prove a t𝑡t-degree version of Theorem 17. Its proof is combinatorial and works, in particular, for s=1𝑠1s=1 and n2k+2𝑛2𝑘2n\geq 2k+2.

Theorem 19.

If n2k+2>2𝑛2𝑘22n\geq 2k+2>2, then for any intersecting family \mathcal{F} of k𝑘k-subsets of [n]delimited-[]𝑛[n] we have δ1()(n2k2)subscript𝛿1binomial𝑛2𝑘2\delta_{1}(\mathcal{F})\leq{n-2\choose k-2}. More generally, if n2k+3t1tk𝑛2𝑘3𝑡1𝑡𝑘n\geq 2k+\frac{3t}{1-\frac{t}{k}} and 1t<k1𝑡𝑘1\leq t<k, then δt()(nt1kt1)subscript𝛿𝑡binomial𝑛𝑡1𝑘𝑡1\delta_{t}(\mathcal{F})\leq{n-t-1\choose k-t-1}.

In the second theorem we give a t𝑡t-degree version of Theorem 18 with much weaker restrictions on n𝑛n for large k𝑘k.

Theorem 20.

If t=1𝑡1t=1, n2k+5𝑛2𝑘5n\geq 2k+5, and k35𝑘35k\geq 35, or 1<tk421𝑡𝑘421<t\leq\frac{k}{4}-2, n2k+14t𝑛2𝑘14𝑡n\geq 2k+14t, then for any non-trivial intersecting family \mathcal{F} of k𝑘k-subsets of [n]delimited-[]𝑛[n] we have δt()(nt1kt1)(ntk1kt1)subscript𝛿𝑡binomial𝑛𝑡1𝑘𝑡1binomial𝑛𝑡𝑘1𝑘𝑡1\delta_{t}(\mathcal{F})\leq{n-t-1\choose k-t-1}-{n-t-k-1\choose k-t-1}.

After writing a preliminary version of the paper, we read the paper [13], where Theorem 19 is proven for s=1𝑠1s=1 and n3k𝑛3𝑘n\geq 3k. It turned out that the approach the authors took is very similar to the approach we use to prove Theorem 19. However, it seems that their proof, unlike ours, does not work for n=2k+2𝑛2𝑘2n=2k+2, which is probably due to the fact that they use the original Frankl’s degree theorem (see Section 2).

5.1 Calculations

In this section we do some of the calculations used in the proofs of Theorems 19 and 20. Note that, substituting u=3𝑢3u=3 in (1), we get that

||(n1k1)+(n4k3)(n4k1)=(n2k2)+(n3k2)+(n4k2)+(n4k3)=binomial𝑛1𝑘1binomial𝑛4𝑘3binomial𝑛4𝑘1binomial𝑛2𝑘2binomial𝑛3𝑘2binomial𝑛4𝑘2binomial𝑛4𝑘3absent|\mathcal{F}|\leq{n-1\choose k-1}+{n-4\choose k-3}-{n-4\choose k-1}={n-2\choose k-2}+{n-3\choose k-2}+{n-4\choose k-2}+{n-4\choose k-3}=
(n2k2)+2(n3k2)=[k1n1+2(k1)(nk)(n2)(n1)](n1k1)=binomial𝑛2𝑘22binomial𝑛3𝑘2delimited-[]𝑘1𝑛12𝑘1𝑛𝑘𝑛2𝑛1binomial𝑛1𝑘1absent{n-2\choose k-2}+2{n-3\choose k-2}=\Big{[}\frac{k-1}{n-1}+\frac{2(k-1)(n-k)}{(n-2)(n-1)}\Big{]}{n-1\choose k-1}=
(k1)(3n2k2)(n1)(n2)(n1k1)=k(k1)(3n2k2)n(n1)(n2)(nk).𝑘13𝑛2𝑘2𝑛1𝑛2binomial𝑛1𝑘1𝑘𝑘13𝑛2𝑘2𝑛𝑛1𝑛2binomial𝑛𝑘\frac{(k-1)(3n-2k-2)}{(n-1)(n-2)}{n-1\choose k-1}=\frac{k(k-1)(3n-2k-2)}{n(n-1)(n-2)}{n\choose k}. (19)

We also have

(nu1nk1)(nu1k1)=i=1nk1nuiii=1k1nuii=i=knk1nuii=i=knk1nuin1i.binomial𝑛𝑢1𝑛𝑘1binomial𝑛𝑢1𝑘1superscriptsubscriptproduct𝑖1𝑛𝑘1𝑛𝑢𝑖𝑖superscriptsubscriptproduct𝑖1𝑘1𝑛𝑢𝑖𝑖superscriptsubscriptproduct𝑖𝑘𝑛𝑘1𝑛𝑢𝑖𝑖superscriptsubscriptproduct𝑖𝑘𝑛𝑘1𝑛𝑢𝑖𝑛1𝑖\frac{{n-u-1\choose n-k-1}}{{n-u-1\choose k-1}}=\frac{\prod_{i=1}^{n-k-1}\frac{n-u-i}{i}}{\prod_{i=1}^{k-1}\frac{n-u-i}{i}}=\prod_{i=k}^{n-k-1}\frac{n-u-i}{i}=\prod_{i=k}^{n-k-1}\frac{n-u-i}{n-1-i}.

Clearly, for 3uk3𝑢𝑘3\leq u\leq k the last expression is maximized for u3𝑢3u\geq 3, and we get the following bound, provided n2k+2𝑛2𝑘2n\geq 2k+2:

(nu1nk1)(nu1k1)i=knk1n3in1i=(k1)(k2)(nk1)(nk2)for 3uk.formulae-sequencebinomial𝑛𝑢1𝑛𝑘1binomial𝑛𝑢1𝑘1superscriptsubscriptproduct𝑖𝑘𝑛𝑘1𝑛3𝑖𝑛1𝑖𝑘1𝑘2𝑛𝑘1𝑛𝑘2for 3𝑢𝑘\frac{{n-u-1\choose n-k-1}}{{n-u-1\choose k-1}}\geq\prod_{i=k}^{n-k-1}\frac{n-3-i}{n-1-i}=\frac{(k-1)(k-2)}{(n-k-1)(n-k-2)}\ \ \ \ \ \ \text{for }3\leq u\leq k. (20)

If n=2k+1𝑛2𝑘1n=2k+1, then we get that the ratio is at least k3k1𝑘3𝑘1\frac{k-3}{k-1}.

We will also use the following formula:

(ntk1kt1)(nt1kt1)=i=1knk+1inti.binomial𝑛𝑡𝑘1𝑘𝑡1binomial𝑛𝑡1𝑘𝑡1superscriptsubscriptproduct𝑖1𝑘𝑛𝑘1𝑖𝑛𝑡𝑖\frac{{n-t-k-1\choose k-t-1}}{{n-t-1\choose k-t-1}}=\prod_{i=1}^{k}\frac{n-k+1-i}{n-t-i}. (21)

5.2 Proof of Theorem 19

Take an intersecting family \mathcal{F} with maximum degree ΔΔ\Delta and diversity γ𝛾\gamma. Then, by definition, ||=Δ+γΔ𝛾|\mathcal{F}|=\Delta+\gamma. W.l.o.g., we suppose that the element 111 has the largest degree.

Proposition 5.

Fix some n,t,k𝑛𝑡𝑘n,t,k. If for an intersecting family of k𝑘k-sets 2[n]superscript2delimited-[]𝑛\mathcal{F}\subset 2^{[n]} with maximum degree ΔΔ\Delta and diversity γ𝛾\gamma we have

Δ+kktγ(n1k1),Δ𝑘𝑘𝑡𝛾binomial𝑛1𝑘1\Delta+\frac{k}{k-t}\gamma\leq{n-1\choose k-1}, (22)

then δt()(nt1kt1)subscript𝛿𝑡binomial𝑛𝑡1𝑘𝑡1\delta_{t}(\mathcal{F})\leq{n-t-1\choose k-t-1}.

Proof.

The sum of t𝑡t-degrees of all t𝑡t-subsets of [2,n]2𝑛[2,n] is γ(kt)+Δ(k1t).𝛾binomial𝑘𝑡Δbinomial𝑘1𝑡\gamma{k\choose t}+\Delta{k-1\choose t}. Therefore, there is a t𝑡t-tuple T𝑇T of elements in [2,n]2𝑛[2,n], such that

δt(T)γ(kt)+Δ(k1t)(n1t)=γi=1tki+1ni+Δi=1tkini.subscript𝛿𝑡𝑇𝛾binomial𝑘𝑡Δbinomial𝑘1𝑡binomial𝑛1𝑡𝛾superscriptsubscriptproduct𝑖1𝑡𝑘𝑖1𝑛𝑖Δsuperscriptsubscriptproduct𝑖1𝑡𝑘𝑖𝑛𝑖\delta_{t}(T)\leq\frac{\gamma{k\choose t}+\Delta{k-1\choose t}}{{n-1\choose t}}=\gamma\prod_{i=1}^{t}\frac{k-i+1}{n-i}+\Delta\prod_{i=1}^{t}\frac{k-i}{n-i}. (23)

The ratio of two fractions is

i=1tki+1nii=1tkini=i=1tki+1ki=kkt.superscriptsubscriptproduct𝑖1𝑡𝑘𝑖1𝑛𝑖superscriptsubscriptproduct𝑖1𝑡𝑘𝑖𝑛𝑖superscriptsubscriptproduct𝑖1𝑡𝑘𝑖1𝑘𝑖𝑘𝑘𝑡\frac{\prod_{i=1}^{t}\frac{k-i+1}{n-i}}{\prod_{i=1}^{t}\frac{k-i}{n-i}}=\prod_{i=1}^{t}\frac{k-i+1}{k-i}=\frac{k}{k-t}.

Therefore, if (22) holds, then

δt()i=1tkini(Δ+kktγ)i=1tkini(n1k1)=(nt1kt1).subscript𝛿𝑡superscriptsubscriptproduct𝑖1𝑡𝑘𝑖𝑛𝑖Δ𝑘𝑘𝑡𝛾superscriptsubscriptproduct𝑖1𝑡𝑘𝑖𝑛𝑖binomial𝑛1𝑘1binomial𝑛𝑡1𝑘𝑡1\delta_{t}(\mathcal{F})\leq\prod_{i=1}^{t}\frac{k-i}{n-i}(\Delta+\frac{k}{k-t}\gamma)\leq\prod_{i=1}^{t}\frac{k-i}{n-i}{n-1\choose k-1}={n-t-1\choose k-t-1}. (24)

To prove Theorem 19, we are only left to verify (22) for all intersecting families. It is vacuously true for trivial intersecting families, so we may assume that γ1𝛾1\gamma\geq 1. Fix \mathcal{F} as in the theorem. We have two cases to distinguish.

Case 1. γ(n4k3)𝛾binomial𝑛4𝑘3\gamma\leq{n-4\choose k-3}. We only need to show that (1) holds. We may apply Corollary 1 (otherwise, it is not difficult to obtain via direct calculations). We only have to check that

kktnk3k3.𝑘𝑘𝑡𝑛𝑘3𝑘3\frac{k}{k-t}\leq\frac{n-k-3}{k-3}. (25)

Putting n=2k+s𝑛2𝑘𝑠n=2k+s, where s1𝑠1s\geq 1, we see that, if t=1𝑡1t=1, then (25) holds for any s1𝑠1s\geq 1. If t>1𝑡1t>1, then we must have

k23k(k3)t+s(kt)k23k,superscript𝑘23𝑘𝑘3𝑡𝑠𝑘𝑡superscript𝑘23𝑘k^{2}-3k-(k-3)t+s(k-t)\geq k^{2}-3k,

which is satisfied when

sk3kttst1tk.formulae-sequence𝑠𝑘3𝑘𝑡𝑡𝑠𝑡1𝑡𝑘s\geq\frac{k-3}{k-t}t\ \ \ \Leftarrow\ \ \ s\geq\frac{t}{1-\frac{t}{k}}.

Case 2. γ(n4k3)𝛾binomial𝑛4𝑘3\gamma\geq{n-4\choose k-3}. By the calculations in Section 5.1, We know that ||(n2k2)+2(n3k2)binomial𝑛2𝑘22binomial𝑛3𝑘2|\mathcal{F}|\leq{n-2\choose k-2}+2{n-3\choose k-2}, and we use the following easy bound on δt()::subscript𝛿𝑡absent\delta_{t}(\mathcal{F}):

δt()(kt)(nt)||.subscript𝛿𝑡binomial𝑘𝑡binomial𝑛𝑡\delta_{t}(\mathcal{F})\leq\frac{{k\choose t}}{{n\choose t}}|\mathcal{F}|. (26)

Thus, it is sufficient for us to check that the following inequality holds:

(nt1kt1)(kt)(nt)[(n2k2)+2(n3k2)].binomial𝑛𝑡1𝑘𝑡1binomial𝑘𝑡binomial𝑛𝑡delimited-[]binomial𝑛2𝑘22binomial𝑛3𝑘2{n-t-1\choose k-t-1}\geq\frac{{k\choose t}}{{n\choose t}}\Big{[}{n-2\choose k-2}+2{n-3\choose k-2}\Big{]}. (27)

We have

(nt1kt1)(nt)(kt)=(nt1)!n!(kt)!(kt1)!(nk)!(nt)!k!=ktnt(nk)binomial𝑛𝑡1𝑘𝑡1binomial𝑛𝑡binomial𝑘𝑡𝑛𝑡1𝑛𝑘𝑡𝑘𝑡1𝑛𝑘𝑛𝑡𝑘𝑘𝑡𝑛𝑡binomial𝑛𝑘\frac{{n-t-1\choose k-t-1}{n\choose t}}{{k\choose t}}=\frac{(n-t-1)!n!(k-t)!}{(k-t-1)!(n-k)!(n-t)!k!}=\frac{k-t}{n-t}{n\choose k} (28)

and, by the calculation in Section 5.1,

(n2k2)+2(n3k2)=k(k1)(3n2k2)n(n1)(n2)(nk).binomial𝑛2𝑘22binomial𝑛3𝑘2𝑘𝑘13𝑛2𝑘2𝑛𝑛1𝑛2binomial𝑛𝑘{n-2\choose k-2}+2{n-3\choose k-2}=\frac{k(k-1)(3n-2k-2)}{n(n-1)(n-2)}{n\choose k}.

Therefore, (27) is equivalent to

ktntk(k1)(3n2k2)n(n1)(n2).𝑘𝑡𝑛𝑡𝑘𝑘13𝑛2𝑘2𝑛𝑛1𝑛2\frac{k-t}{n-t}\geq\frac{k(k-1)(3n-2k-2)}{n(n-1)(n-2)}.

If t=1𝑡1t=1, then it simplifies to k(3n2k2)n(n2)1𝑘3𝑛2𝑘2𝑛𝑛21\frac{k(3n-2k-2)}{n(n-2)}\leq 1, which holds for any n2k+2𝑛2𝑘2n\geq 2k+2.

If t>1𝑡1t>1, then it simplifies to a quadratic inequality in n𝑛n, which holds for

n2k2+(k3)t+(2k2+(k3)t)28(kt)t(k21)2(kt).𝑛2superscript𝑘2𝑘3𝑡superscript2superscript𝑘2𝑘3𝑡28𝑘𝑡𝑡superscript𝑘212𝑘𝑡n\geq\frac{2k^{2}+(k-3)t+\sqrt{(2k^{2}+(k-3)t)^{2}-8(k-t)t(k^{2}-1)}}{2(k-t)}.

The right hand side is at most

2k2+(k3)t+(2k2+(k3)t)22(kt)=2k2+(k3)t(kt)=2k+3(k1)tkt<2k+3t1tk.2superscript𝑘2𝑘3𝑡superscript2superscript𝑘2𝑘3𝑡22𝑘𝑡2superscript𝑘2𝑘3𝑡𝑘𝑡2𝑘3𝑘1𝑡𝑘𝑡2𝑘3𝑡1𝑡𝑘\frac{2k^{2}+(k-3)t+\sqrt{(2k^{2}+(k-3)t)^{2}}}{2(k-t)}=\frac{2k^{2}+(k-3)t}{(k-t)}=2k+\frac{3(k-1)t}{k-t}<2k+\frac{3t}{1-\frac{t}{k}}.

5.3 Proof of Theorem 20

The strategy of the proof is very similar to that of Theorem 19. Fix a non-trivial intersecting family \mathcal{F} with γ2𝛾2\gamma\geq 2 (otherwise, it is a subfamily of some Hilton-Milner family). W.l.o.g., suppose that the element of the family \mathcal{F} with maximal degree is 1, and that \mathcal{F} contains the set [2,k+1]2𝑘1[2,k+1]. Then any other set containing 111 must intersect U𝑈U. We compare \mathcal{F} with the Hilton-Milner family :={F:1F,F[2,k+1]}[2,k+1].assignconditional-set𝐹formulae-sequence1𝐹𝐹2𝑘12𝑘1\mathcal{HM}:=\{F:1\in F,F\cap[2,k+1]\neq\emptyset\}\cup[2,k+1]. We consider cases depending on γ𝛾\gamma. The case analysis, however, will be more complicated, as compared to the previous case. Notably, we get a new non-trivial Case 1.

Case 1. 1<γ<(nk+t+1t+2)1𝛾binomial𝑛𝑘𝑡1𝑡21<\gamma<{n-k+t+1\choose t+2}. We have γ2𝛾2\gamma\geq 2, and we may apply Theorem 4 to the families (1):={F{1}:1F}assign1conditional-set𝐹11𝐹\mathcal{F}(1):=\{F\setminus\{1\}:1\in F\in\mathcal{F}\} and (1¯):={F:1F}assign¯1conditional-set𝐹1𝐹\mathcal{F}(\bar{1}):=\{F:1\notin F\in\mathcal{F}\}. We get that the cardinality of (1)1\mathcal{F}(1) is at most the cardinality of all (k1)𝑘1(k-1)-subsets of [2,n]2𝑛[2,n] that intersect the sets [2,k+1]2𝑘1[2,k+1] and [2,k]{k+2}2𝑘𝑘2[2,k]\cup\{k+2\}. In other words, the degree of 111 is at most (n1k1)(nk1k1)(nk2k2)binomial𝑛1𝑘1binomial𝑛𝑘1𝑘1binomial𝑛𝑘2𝑘2{n-1\choose k-1}-{n-k-1\choose k-1}-{n-k-2\choose k-2}. That is, some (nk2k2)binomial𝑛𝑘2𝑘2{n-k-2\choose k-2} sets from \mathcal{HM} containing 111 are missing from \mathcal{F}.

Denote 𝒢:={G([n]k):1G,G[2,k+1]}assign𝒢conditional-set𝐺binomialdelimited-[]𝑛𝑘formulae-sequence1𝐺𝐺2𝑘1\mathcal{G}:=\{G\in{[n]\choose k}\setminus\mathcal{F}:1\in G,G\cap[2,k+1]\neq\emptyset\}. By the paragraph above, we have |𝒢|(nk2k2)𝒢binomial𝑛𝑘2𝑘2|\mathcal{G}|\geq{n-k-2\choose k-2}. Consider a subfamily 𝒢𝒢superscript𝒢𝒢\mathcal{G}^{\prime}\subset\mathcal{G}, such that each G𝒢superscript𝐺superscript𝒢G^{\prime}\in\mathcal{G}^{\prime} intersects [k+2,n]𝑘2𝑛[k+2,n] in at least t𝑡t elements.

Then, denoting by \mathcal{H} the Hilton-Milner family, it is easy to see that the following rough estimate holds.

δt()δt()|𝒢|(nk1t)γ.subscript𝛿𝑡subscript𝛿𝑡superscript𝒢binomial𝑛𝑘1𝑡𝛾\delta_{t}(\mathcal{H})-\delta_{t}(\mathcal{F})\geq\frac{|\mathcal{G}^{\prime}|}{{n-k-1\choose t}}-\gamma. (29)

Indeed, the first summand is the average loss in the t𝑡t-degree of t𝑡t-sets in [k+2,n]𝑘2𝑛[k+2,n], and each set contributing to γ𝛾\gamma can contribute at most 1 to minimum t𝑡t-degree. In the rest of this case our goal is to show that the RHS in (29) is always positive.

Let us first estimate the size of 𝒢superscript𝒢\mathcal{G}^{\prime}. To do so, we have to exclude all the sets that intersect [1,k+1]1𝑘1[1,k+1] in more than kt𝑘𝑡k-t elements. Since 111 is always in the set, the number of sets we have to exclude is

i=ktk1(ki)(nk1ki1).superscriptsubscript𝑖𝑘𝑡𝑘1binomial𝑘𝑖binomial𝑛𝑘1𝑘𝑖1\sum_{i=k-t}^{k-1}{k\choose i}{n-k-1\choose k-i-1}.

We have (nk1tj)>2(nk1tj1)binomial𝑛𝑘1𝑡𝑗2binomial𝑛𝑘1𝑡𝑗1{n-k-1\choose t-j}>2{n-k-1\choose t-j-1} for any j0𝑗0j\geq 0, since n2k8t𝑛2𝑘8𝑡n\geq 2k\geq 8t. Therefore, the sum above is at most

(kkt)(nk1t)=(kt)(nk1t),binomial𝑘𝑘𝑡binomial𝑛𝑘1𝑡binomial𝑘𝑡binomial𝑛𝑘1𝑡{k\choose k-t}{n-k-1\choose t}={k\choose t}{n-k-1\choose t},

and we have

|𝒢|(nk2k2)(kt)(nk1t).superscript𝒢binomial𝑛𝑘2𝑘2binomial𝑘𝑡binomial𝑛𝑘1𝑡|\mathcal{G}^{\prime}|\geq{n-k-2\choose k-2}-{k\choose t}{n-k-1\choose t}. (30)

To show that the RHS in (29) is always positive and thus to conclude the proof in Case 1, it is sufficient to show the first in the following chain of inequalities:

(nk2k2)(nk1t)(nk+t+2t+2)>>(nk1t)(nk+t+1t+2)+(kt)(nk1t).binomial𝑛𝑘2𝑘2binomial𝑛𝑘1𝑡binomial𝑛𝑘𝑡2𝑡2binomial𝑛𝑘1𝑡binomial𝑛𝑘𝑡1𝑡2binomial𝑘𝑡binomial𝑛𝑘1𝑡{n-k-2\choose k-2}\geq{n-k-1\choose t}{n-k+t+2\choose t+2}>\\ >{n-k-1\choose t}{n-k+t+1\choose t+2}+{k\choose t}{n-k-1\choose t}. (31)

Note that the second inequality is just a corollary of Newton’s binom and the fact that (kt)<(nk+t+1t+1)binomial𝑘𝑡binomial𝑛𝑘𝑡1𝑡1{k\choose t}<{n-k+t+1\choose t+1}. We also use the fact that γ(nk+t+1t+2)𝛾binomial𝑛𝑘𝑡1𝑡2\gamma\leq{n-k+t+1\choose t+2}.

If t=1𝑡1t=1, n2k+5𝑛2𝑘5n\geq 2k+5, then in the worst case for (31) is n=2k+5𝑛2𝑘5n=2k+5, and the first inequality in (31) transforms into

(k+35)(k+4)(k+83),binomial𝑘35𝑘4binomial𝑘83{k+3\choose 5}\geq(k+4){k+8\choose 3},

which holds for k35𝑘35k\geq 35.

If 1<tk421𝑡𝑘421<t\leq\frac{k}{4}-2, n2k+14t𝑛2𝑘14𝑡n\geq 2k+14t, then we have

(nk1t)(nk+t+2t+2)(nk+t+2)!t!(t+2)!(nkt)!=(nk+t+22t+2)(2t+2t)binomial𝑛𝑘1𝑡binomial𝑛𝑘𝑡2𝑡2𝑛𝑘𝑡2𝑡𝑡2𝑛𝑘𝑡binomial𝑛𝑘𝑡22𝑡2binomial2𝑡2𝑡absent{n-k-1\choose t}{n-k+t+2\choose t+2}\leq\frac{(n-k+t+2)!}{t!(t+2)!(n-k-t)!}={n-k+t+2\choose 2t+2}{2t+2\choose t}\leq
(nk+t+22t+2)22t,binomial𝑛𝑘𝑡22𝑡2superscript22𝑡{n-k+t+2\choose 2t+2}2^{2t},

where the last inequality holds for any t2𝑡2t\geq 2. On the other hand, using the above conditions on n,k,t𝑛𝑘𝑡n,k,t, we have

(nk+t+22t+2)<(nk2nk2t4)t+4(nk22t+2)binomial𝑛𝑘𝑡22𝑡2superscript𝑛𝑘2𝑛𝑘2𝑡4𝑡4binomial𝑛𝑘22𝑡2absent{n-k+t+2\choose 2t+2}<\Big{(}\frac{n-k-2}{n-k-2t-4}\Big{)}^{t+4}{n-k-2\choose 2t+2}\leq
(1+2t+2k+10t4)t+4(nk22t+2)(1916)t+4(nk22t+2)<superscript12𝑡2𝑘10𝑡4𝑡4binomial𝑛𝑘22𝑡2superscript1916𝑡4binomial𝑛𝑘22𝑡2absent\Big{(}1+\frac{2t+2}{k+10t-4}\Big{)}^{t+4}{n-k-2\choose 2t+2}\leq\Big{(}\frac{19}{16}\Big{)}^{t+4}{n-k-2\choose 2t+2}<
(54)t+4(4t+4nk4t6)2t+2(nk24t+4)(54)t+4(4t+414t+2)2t+2(nk24t+4)superscript54𝑡4superscript4𝑡4𝑛𝑘4𝑡62𝑡2binomial𝑛𝑘24𝑡4superscript54𝑡4superscript4𝑡414𝑡22𝑡2binomial𝑛𝑘24𝑡4absent\Big{(}\frac{5}{4}\Big{)}^{t+4}\Big{(}\frac{4t+4}{n-k-4t-6}\Big{)}^{2t+2}{n-k-2\choose 4t+4}\leq\Big{(}\frac{5}{4}\Big{)}^{t+4}\Big{(}\frac{4t+4}{14t+2}\Big{)}^{2t+2}{n-k-2\choose 4t+4}\leq
(54)t+4(25)2t+2(nk24t+4)(12)2t+2(nk2k2).superscript54𝑡4superscript252𝑡2binomial𝑛𝑘24𝑡4superscript122𝑡2binomial𝑛𝑘2𝑘2\Big{(}\frac{5}{4}\Big{)}^{t+4}\Big{(}\frac{2}{5}\Big{)}^{2t+2}{n-k-2\choose 4t+4}\leq\Big{(}\frac{1}{2}\Big{)}^{2t+2}{n-k-2\choose k-2}.

Comparing this chain of inequalities with the one above, we conclude that for our choice of parameters

(nk2k2)(nk1t)(nk+t+2t+2)22t+222t>1.binomial𝑛𝑘2𝑘2binomial𝑛𝑘1𝑡binomial𝑛𝑘𝑡2𝑡2superscript22𝑡2superscript22𝑡1\frac{{n-k-2\choose k-2}}{{n-k-1\choose t}{n-k+t+2\choose t+2}}\geq\frac{2^{2t+2}}{2^{2t}}>1.

Case 2. (nk+t+1t+2)γ(n4k3)binomial𝑛𝑘𝑡1𝑡2𝛾binomial𝑛4𝑘3{n-k+t+1\choose t+2}\leq\gamma\leq{n-4\choose k-3}. Using the first inequality in (24), we get the following analogue of Statement 5.

Statement 1.

Fix some n,t,k𝑛𝑡𝑘n,t,k. If for an intersecting family of k𝑘k-sets 2[n]superscript2delimited-[]𝑛\mathcal{F}\subset 2^{[n]} with maximum degree ΔΔ\Delta and diversity γ𝛾\gamma we have

Δ+ctγ(1i=1knk+1inti)(n1k1),Δsubscript𝑐𝑡𝛾1superscriptsubscriptproduct𝑖1𝑘𝑛𝑘1𝑖𝑛𝑡𝑖binomial𝑛1𝑘1\Delta+c_{t}\gamma\leq\Big{(}1-\prod_{i=1}^{k}\frac{n-k+1-i}{n-t-i}\Big{)}{n-1\choose k-1}, (32)

then δt()(nt1kt1)(ntk1kt1)subscript𝛿𝑡binomial𝑛𝑡1𝑘𝑡1binomial𝑛𝑡𝑘1𝑘𝑡1\delta_{t}(\mathcal{F})\leq{n-t-1\choose k-t-1}-{n-t-k-1\choose k-t-1}.

Proof.

Indeed, if (32) holds, then, using (24), we get

δt()i=1tkini(1i=1knk+1inti)(n1k1)=subscript𝛿𝑡superscriptsubscriptproduct𝑖1𝑡𝑘𝑖𝑛𝑖1superscriptsubscriptproduct𝑖1𝑘𝑛𝑘1𝑖𝑛𝑡𝑖binomial𝑛1𝑘1absent\delta_{t}(\mathcal{F})\leq\prod_{i=1}^{t}\frac{k-i}{n-i}\Big{(}1-\prod_{i=1}^{k}\frac{n-k+1-i}{n-t-i}\Big{)}{n-1\choose k-1}=
(nt1kt1)(1i=1knk+1inti)=(21)(nt1kt1)(ntk1kt1).binomial𝑛𝑡1𝑘𝑡11superscriptsubscriptproduct𝑖1𝑘𝑛𝑘1𝑖𝑛𝑡𝑖italic-(21italic-)binomial𝑛𝑡1𝑘𝑡1binomial𝑛𝑡𝑘1𝑘𝑡1{n-t-1\choose k-t-1}\Big{(}1-\prod_{i=1}^{k}\frac{n-k+1-i}{n-t-i}\Big{)}\overset{\eqref{eq07}}{=}{n-t-1\choose k-t-1}-{n-t-k-1\choose k-t-1}.

We apply (1). Our situation corresponds to the case ukt2𝑢𝑘𝑡2u\leq k-t-2. To verify (32), one has to check that

(nu1k1)ct(nu1nk1)i=1knk+1inti(n1k1)0.binomial𝑛𝑢1𝑘1subscript𝑐𝑡binomial𝑛𝑢1𝑛𝑘1superscriptsubscriptproduct𝑖1𝑘𝑛𝑘1𝑖𝑛𝑡𝑖binomial𝑛1𝑘10{n-u-1\choose k-1}-c_{t}{n-u-1\choose n-k-1}-\prod_{i=1}^{k}\frac{n-k+1-i}{n-t-i}{n-1\choose k-1}\geq 0. (33)

We have

(nu1k1)ct(nu1nk1)=(1kkti=knk1nuin1i)(nu1k1)(20)binomial𝑛𝑢1𝑘1subscript𝑐𝑡binomial𝑛𝑢1𝑛𝑘11𝑘𝑘𝑡superscriptsubscriptproduct𝑖𝑘𝑛𝑘1𝑛𝑢𝑖𝑛1𝑖binomial𝑛𝑢1𝑘1italic-(20italic-){n-u-1\choose k-1}-c_{t}{n-u-1\choose n-k-1}=\Big{(}1-\frac{k}{k-t}\prod_{i=k}^{n-k-1}\frac{n-u-i}{n-1-i}\Big{)}{n-u-1\choose k-1}\overset{\eqref{eq04}}{\geq}
(1k(k1)(k2)(kt)(nk1)(nk2))i=1k1nuini(n1k1).1𝑘𝑘1𝑘2𝑘𝑡𝑛𝑘1𝑛𝑘2superscriptsubscriptproduct𝑖1𝑘1𝑛𝑢𝑖𝑛𝑖binomial𝑛1𝑘1\Big{(}1-\frac{k(k-1)(k-2)}{(k-t)(n-k-1)(n-k-2)}\Big{)}\prod_{i=1}^{k-1}\frac{n-u-i}{n-i}{n-1\choose k-1}.

The last expression is minimized when u=kt2𝑢𝑘𝑡2u=k-t-2. Comparing the product above with the product in (33), we get

i=1knk+1intii=1k1nuinii=1knk+1intii=1k1nk+t+2ini=i=1kt1nktintii=1kt2nkinisuperscriptsubscriptproduct𝑖1𝑘𝑛𝑘1𝑖𝑛𝑡𝑖superscriptsubscriptproduct𝑖1𝑘1𝑛𝑢𝑖𝑛𝑖superscriptsubscriptproduct𝑖1𝑘𝑛𝑘1𝑖𝑛𝑡𝑖superscriptsubscriptproduct𝑖1𝑘1𝑛𝑘𝑡2𝑖𝑛𝑖superscriptsubscriptproduct𝑖1𝑘𝑡1𝑛𝑘𝑡𝑖𝑛𝑡𝑖superscriptsubscriptproduct𝑖1𝑘𝑡2𝑛𝑘𝑖𝑛𝑖absent\frac{\prod_{i=1}^{k}\frac{n-k+1-i}{n-t-i}}{\prod_{i=1}^{k-1}\frac{n-u-i}{n-i}}\leq\frac{\prod_{i=1}^{k}\frac{n-k+1-i}{n-t-i}}{\prod_{i=1}^{k-1}\frac{n-k+t+2-i}{n-i}}=\frac{\prod_{i=1}^{k-t-1}\frac{n-k-t-i}{n-t-i}}{\prod_{i=1}^{k-t-2}\frac{n-k-i}{n-i}}\leq
i=1kt1nktintii=1kt2nktinti=1knk+1.superscriptsubscriptproduct𝑖1𝑘𝑡1𝑛𝑘𝑡𝑖𝑛𝑡𝑖superscriptsubscriptproduct𝑖1𝑘𝑡2𝑛𝑘𝑡𝑖𝑛𝑡𝑖1𝑘𝑛𝑘1\frac{\prod_{i=1}^{k-t-1}\frac{n-k-t-i}{n-t-i}}{\prod_{i=1}^{k-t-2}\frac{n-k-t-i}{n-t-i}}=1-\frac{k}{n-k+1}.

Therefore, to prove (33), it is sufficient for us to show that

1k(k1)(k2)(kt)(nk1)(nk2)1knk+1.1𝑘𝑘1𝑘2𝑘𝑡𝑛𝑘1𝑛𝑘21𝑘𝑛𝑘11-\frac{k(k-1)(k-2)}{(k-t)(n-k-1)(n-k-2)}\geq 1-\frac{k}{n-k+1}. (34)

For the fraction in the left hand side, we use the following property: if we add 1 to one of the multiples in the numerator and 1 to one of the multiples in the denominator, then the fraction will only increase, and the expression in the left hand side will decrease. If t=1𝑡1t=1, then the LHS of (34) is

1k(k2)(nk1)(nk2)1k2(nk+1)(nk2)>1knk+1,1𝑘𝑘2𝑛𝑘1𝑛𝑘21superscript𝑘2𝑛𝑘1𝑛𝑘21𝑘𝑛𝑘11-\frac{k(k-2)}{(n-k-1)(n-k-2)}\geq 1-\frac{k^{2}}{(n-k+1)(n-k-2)}>1-\frac{k}{n-k+1},

and therefore (33) is satisfied for any k𝑘k and n2k+2𝑛2𝑘2n\geq 2k+2.

If 1<tk41𝑡𝑘41<t\leq\frac{k}{4} and n2k+4t𝑛2𝑘4𝑡n\geq 2k+4t, then (kt)(nk1)(kt)(k+4t1)=k2+3kt4t2k+t>k2𝑘𝑡𝑛𝑘1𝑘𝑡𝑘4𝑡1superscript𝑘23𝑘𝑡4superscript𝑡2𝑘𝑡superscript𝑘2(k-t)(n-k-1)\geq(k-t)(k+4t-1)=k^{2}+3kt-4t^{2}-k+t>k^{2}, and, therefore, the LHS of (34) is at least

1k3(kt)(nk1)(nk+1)>1knk+1,1superscript𝑘3𝑘𝑡𝑛𝑘1𝑛𝑘11𝑘𝑛𝑘11-\frac{k^{3}}{(k-t)(n-k-1)(n-k+1)}>1-\frac{k}{n-k+1},

and (33) is satisfied again.

Case 3. γ(n4k3)𝛾binomial𝑛4𝑘3\gamma\geq{n-4\choose k-3}. As in Case 2 of the proof of Theorem 19, we know that (26) holds. We have to verify that

(nt1kt1)(ntk1kt1)(kt)(nt)[(n2k2)+2(n3k2)]binomial𝑛𝑡1𝑘𝑡1binomial𝑛𝑡𝑘1𝑘𝑡1binomial𝑘𝑡binomial𝑛𝑡delimited-[]binomial𝑛2𝑘22binomial𝑛3𝑘2{n-t-1\choose k-t-1}-{n-t-k-1\choose k-t-1}\geq\frac{{k\choose t}}{{n\choose t}}\Big{[}{n-2\choose k-2}+2{n-3\choose k-2}\Big{]} (35)

holds.

Using (19), (21) and (28), the inequality (35) is equivalent to

ktnt(1i=1knk+1inti)k(k1)(3n2k2)n(n1)(n2).𝑘𝑡𝑛𝑡1superscriptsubscriptproduct𝑖1𝑘𝑛𝑘1𝑖𝑛𝑡𝑖𝑘𝑘13𝑛2𝑘2𝑛𝑛1𝑛2\frac{k-t}{n-t}\Big{(}1-\prod_{i=1}^{k}\frac{n-k+1-i}{n-t-i}\Big{)}\geq\frac{k(k-1)(3n-2k-2)}{n(n-1)(n-2)}. (36)

If t=1𝑡1t=1, then it simplifies to

(1i=1knk+1in1i)k(3n2k2)n(n2)(nk)(n2k2)n(n2)i=1knk+1in1i.formulae-sequence1superscriptsubscriptproduct𝑖1𝑘𝑛𝑘1𝑖𝑛1𝑖𝑘3𝑛2𝑘2𝑛𝑛2𝑛𝑘𝑛2𝑘2𝑛𝑛2superscriptsubscriptproduct𝑖1𝑘𝑛𝑘1𝑖𝑛1𝑖\Big{(}1-\prod_{i=1}^{k}\frac{n-k+1-i}{n-1-i}\Big{)}\geq\frac{k(3n-2k-2)}{n(n-2)}\ \ \Leftrightarrow\ \ \frac{(n-k)(n-2k-2)}{n(n-2)}\geq\prod_{i=1}^{k}\frac{n-k+1-i}{n-1-i}.

This is equivalent to

(n2k2)ni=2knk+1in1i.𝑛2𝑘2𝑛superscriptsubscriptproduct𝑖2𝑘𝑛𝑘1𝑖𝑛1𝑖\frac{(n-2k-2)}{n}\geq\prod_{i=2}^{k}\frac{n-k+1-i}{n-1-i}. (37)

The right hand side is at most

(n2k+1)(n2k+2)(n3)(n4)(n2k+4)(n2k+2)n(n4).𝑛2𝑘1𝑛2𝑘2𝑛3𝑛4𝑛2𝑘4𝑛2𝑘2𝑛𝑛4\frac{(n-2k+1)(n-2k+2)}{(n-3)(n-4)}\leq\frac{(n-2k+4)(n-2k+2)}{n(n-4)}.

Therefore (37) follows from

n2k2n(n2k+4)(n2k+2)n(n4)(n2k2)(n4)(n2k+4)(n2k+2),\frac{n-2k-2}{n}\geq\frac{(n-2k+4)(n-2k+2)}{n(n-4)}\ \ \Leftrightarrow(n-2k-2)(n-4)\geq(n-2k+4)(n-2k+2),

which holds for any n2k+4𝑛2𝑘4n\geq 2k+4 and k12.𝑘12k\geq 12.

If 1<tk421𝑡𝑘421<t\leq\frac{k}{4}-2, then

1ntktk(k1)(3n2k2)n(n1)(n2)1k(k1)(3n2k2)(kt)n(n1)=1𝑛𝑡𝑘𝑡𝑘𝑘13𝑛2𝑘2𝑛𝑛1𝑛21𝑘𝑘13𝑛2𝑘2𝑘𝑡𝑛𝑛1absent1-\frac{n-t}{k-t}\cdot\frac{k(k-1)(3n-2k-2)}{n(n-1)(n-2)}\geq 1-\frac{k(k-1)(3n-2k-2)}{(k-t)n(n-1)}=
(kt)n2(3k23kk+t)n+2(k3k)(kt)n(n1)(kt)n23k2n+2k3(kt)n(n1)()𝑘𝑡superscript𝑛23superscript𝑘23𝑘𝑘𝑡𝑛2superscript𝑘3𝑘𝑘𝑡𝑛𝑛1𝑘𝑡superscript𝑛23superscript𝑘2𝑛2superscript𝑘3𝑘𝑡𝑛𝑛1\frac{(k-t)n^{2}-(3k^{2}-3k-k+t)n+2(k^{3}-k)}{(k-t)n(n-1)}\geq\frac{(k-t)n^{2}-3k^{2}n+2k^{3}}{(k-t)n(n-1)}\overset{(*)}{\geq}
(nk)(n2k2+ktkt)n(n1)(nk)(n2k2ktkt)n2(nk)(n2k3t)n2,𝑛𝑘𝑛2superscript𝑘2𝑘𝑡𝑘𝑡𝑛𝑛1𝑛𝑘𝑛2𝑘2𝑘𝑡𝑘𝑡superscript𝑛2𝑛𝑘𝑛2𝑘3𝑡superscript𝑛2\frac{(n-k)(n-2\frac{k^{2}+kt}{k-t})}{n(n-1)}\geq\frac{(n-k)(n-2k-\frac{2kt}{k-t})}{n^{2}}\geq\frac{(n-k)(n-2k-3t)}{n^{2}},

where in the inequality (*) we used the fact that the difference between the first numerator and the second numerator multiplied by by (kt)𝑘𝑡(k-t) is ktn2k2t𝑘𝑡𝑛2superscript𝑘2𝑡ktn-2k^{2}t, which is positive for n>2k𝑛2𝑘n>2k; in the last inequality we used that tk/3𝑡𝑘3t\leq k/3. On the other hand,

i=1knk+1inti=i=1kt1ntkinti(nkn)kt1(nkn)3k4+1.superscriptsubscriptproduct𝑖1𝑘𝑛𝑘1𝑖𝑛𝑡𝑖superscriptsubscriptproduct𝑖1𝑘𝑡1𝑛𝑡𝑘𝑖𝑛𝑡𝑖superscript𝑛𝑘𝑛𝑘𝑡1superscript𝑛𝑘𝑛3𝑘41\prod_{i=1}^{k}\frac{n-k+1-i}{n-t-i}=\prod_{i=1}^{k-t-1}\frac{n-t-k-i}{n-t-i}\leq\Big{(}\frac{n-k}{n}\Big{)}^{k-t-1}\leq\Big{(}\frac{n-k}{n}\Big{)}^{\frac{3k}{4}+1}.

Therefore, combining these calculations, the inequality (36) would follow from the inequality

12k+3tn(1kn)3k/4.12𝑘3𝑡𝑛superscript1𝑘𝑛3𝑘41-\frac{2k+3t}{n}\geq\Big{(}1-\frac{k}{n}\Big{)}^{3k/4}. (38)

If 2k+14tn7k2𝑘14𝑡𝑛7𝑘2k+14t\leq n\leq 7k, then the right hand side of the inequality above is at most e3k24n<ek10,superscript𝑒3superscript𝑘24𝑛superscript𝑒𝑘10e^{-\frac{3k^{2}}{4n}}<e^{-\frac{k}{10}}, while the left hand side is at least 11t2k+14t>222k+2811𝑡2𝑘14𝑡222𝑘28\frac{11t}{2k+14t}>\frac{22}{2k+28}. It is easy to see that, say, for k10𝑘10k\geq 10, 222k+28>ek10222𝑘28superscript𝑒𝑘10\frac{22}{2k+28}>e^{-\frac{k}{10}}.

If n>7k𝑛7𝑘n>7k and k10𝑘10k\geq 10, then

(1kn)3k/4<(1kn)7<17kn+21k2n214kn.superscript1𝑘𝑛3𝑘4superscript1𝑘𝑛717𝑘𝑛21superscript𝑘2superscript𝑛214𝑘𝑛\Big{(}1-\frac{k}{n}\Big{)}^{3k/4}<\Big{(}1-\frac{k}{n}\Big{)}^{7}<1-\frac{7k}{n}+\frac{21k^{2}}{n^{2}}\leq 1-\frac{4k}{n}.

On the other hand, 12k+3tn13kn12𝑘3𝑡𝑛13𝑘𝑛1-\frac{2k+3t}{n}\geq 1-\frac{3k}{n}, therefore, the inequality (38) is verified in this case.

To conclude, we remark that the only conditions on k𝑘k that we used for t2𝑡2t\geq 2 were k4t+8𝑘4𝑡8k\geq 4t+8 and k10𝑘10k\geq 10. The later one is implied by the former one.

6 Degree version of the Erdős Matching Conjecture

The matching number ν()𝜈\nu(\mathcal{F}) of a family \mathcal{F} is the maximum number of pairwise disjoint sets from \mathcal{F}. That is, intersecting families are exactly the families with matching number one. It is a natural question to ask, what is the largest family with matching number (at most) s𝑠s. Speaking of uniform families, let us denote ek(n,s)subscript𝑒𝑘𝑛𝑠e_{k}(n,s) the size of the largest family ([n]k)binomialdelimited-[]𝑛𝑘\mathcal{F}\subset{[n]\choose k} with ν()s𝜈𝑠\nu(\mathcal{F})\leq s. Note that this question is only interesting when nk(s+1)𝑛𝑘𝑠1n\geq k(s+1). The following two families are the natural candidates:

𝒜0(n,k,s):={A[n]:A[s]},assignsubscript𝒜0𝑛𝑘𝑠conditional-set𝐴delimited-[]𝑛𝐴delimited-[]𝑠\mathcal{A}_{0}(n,k,s):=\{A\subset[n]:A\cap[s]\neq\emptyset\},
Ak(k,s):=([k(s+1)1]k).assignsubscript𝐴𝑘𝑘𝑠binomialdelimited-[]𝑘𝑠11𝑘A_{k}(k,s):={[k(s+1)-1]\choose k}.

Erdős conjectured [2] that ek(n,s)=max{|𝒜0(n,k,s)|,|𝒜k(k,s)|}subscript𝑒𝑘𝑛𝑠subscript𝒜0𝑛𝑘𝑠subscript𝒜𝑘𝑘𝑠e_{k}(n,s)=\max\big{\{}|{\mathcal{A}}_{0}(n,k,s)|,|{\mathcal{A}}_{k}(k,s)|\big{\}}. This conjecture is known as the Erős Matching conjecture. It was studied quite extensively over the last 50 years, but it remains unsolved in general. It is known to be true for k3𝑘3k\leq 3 [7] and for n(2s+1)(k1)𝑛2𝑠1𝑘1n\geq(2s+1)(k-1) [6]. We note that 𝒜0(n,k,s)subscript𝒜0𝑛𝑘𝑠{\mathcal{A}}_{0}(n,k,s) is bigger than 𝒜k(k,s)subscript𝒜𝑘𝑘𝑠{\mathcal{A}}_{k}(k,s) already for relatively small n𝑛n: the condition n>(k+1)(s+1)𝑛𝑘1𝑠1n>(k+1)(s+1) should suffice.

A degree version of Erdős Matching Conjecture and related problems attracted a lot of attention recently (see, e.g., [15], [22]). The following theorem was proved in [17].

Theorem 21 ([17]).

Given n,k,s𝑛𝑘𝑠n,k,s with n3k2(s+1)𝑛3superscript𝑘2𝑠1n\geq 3k^{2}(s+1), if for a family ([n]k)binomialdelimited-[]𝑛𝑘\mathcal{F}\subset{[n]\choose k} with ν()s𝜈𝑠\nu(\mathcal{F})\leq s we have δ1()(n1k1)(ns1k1)=δ1(𝒜0(n,k,s))subscript𝛿1binomial𝑛1𝑘1binomial𝑛𝑠1𝑘1subscript𝛿1subscript𝒜0𝑛𝑘𝑠\delta_{1}(\mathcal{F})\leq{n-1\choose k-1}-{n-s-1\choose k-1}=\delta_{1}({\mathcal{A}}_{0}(n,k,s)).

This improved the result of Bollobás, Daykin, and Erdős [1], who arrived at the same conclusion for n2k3s𝑛2superscript𝑘3𝑠n\geq 2k^{3}s. The authors conjectured that the same should hold for any n>k(s+1)𝑛𝑘𝑠1n>k(s+1). Note that in the degree version we do not include the family 𝒜k(k,s)subscript𝒜𝑘𝑘𝑠{\mathcal{A}}_{k}(k,s), since its minimum t𝑡t-degree is 0 for nk(s+1)𝑛𝑘𝑠1n\geq k(s+1) and t1𝑡1t\geq 1. Note that, for general t𝑡t we have δt(𝒜0(n,k,s))=(ntkt)(nstkt)subscript𝛿𝑡subscript𝒜0𝑛𝑘𝑠binomial𝑛𝑡𝑘𝑡binomial𝑛𝑠𝑡𝑘𝑡\delta_{t}({\mathcal{A}}_{0}(n,k,s))={n-t\choose k-t}-{n-s-t\choose k-t}.

In this paper we improve and generalize Theorem 21 above result for k𝑘k large in comparison to s𝑠s.

Theorem 22.

Fix n,s,k𝑛𝑠𝑘n,s,k and t1𝑡1t\geq 1, such that n2k2𝑛2superscript𝑘2n\geq 2k^{2}, and k5st𝑘5𝑠𝑡k\geq 5st (k3s𝑘3𝑠k\geq 3s for t=1𝑡1t=1). For any family ([n]k)binomialdelimited-[]𝑛𝑘\mathcal{F}\subset{[n]\choose k} with ν()s𝜈𝑠\nu(\mathcal{F})\leq s we have δt()δ(𝒜0(n,k,s))subscript𝛿𝑡𝛿subscript𝒜0𝑛𝑘𝑠\delta_{t}(\mathcal{F})\leq\delta({\mathcal{A}}_{0}(n,k,s)), with equality only in the case =𝒜0(n,k,s)subscript𝒜0𝑛𝑘𝑠\mathcal{F}={\mathcal{A}}_{0}(n,k,s).

We note that the constants in the proof are not optimal, and chosen in this way to simplify the calculations. In the proof we make use of the stability theorem, proved by the author together with P. Frankl [10, 11]. Recall that τ()𝜏\tau(\mathcal{F}) is the minimal size of a set S[n]𝑆delimited-[]𝑛S\subset[n], such that SF𝑆𝐹S\cap F\neq\emptyset for any F𝐹F\in\mathcal{F}. For fixed n,s,k𝑛𝑠𝑘n,s,k, saying that ([n]k)binomialdelimited-[]𝑛𝑘\mathcal{F}\subset{[n]\choose k} satisfies ν()s𝜈𝑠\nu(\mathcal{F})\leq s and τ()>s𝜏𝑠\tau(\mathcal{F})>s is equivalent to saying that \mathcal{F} is not isomorphic to a subfamily of 𝒜0(n,k,s)subscript𝒜0𝑛𝑘𝑠\mathcal{A}_{0}(n,k,s).

Theorem 23 ([10]).

Let n=(u+s1)(k1)+s+k,𝑛𝑢𝑠1𝑘1𝑠𝑘n=(u+s-1)(k-1)+s+k, us+1𝑢𝑠1u\geq s+1. Then for any family 𝒢([n]k)𝒢binomialdelimited-[]𝑛𝑘\mathcal{G}\subset{[n]\choose k} with ν(𝒢)=s𝜈𝒢𝑠\nu(\mathcal{G})=s and τ(𝒢)s+1𝜏𝒢𝑠1\tau(\mathcal{G})\geq s+1 we have

|𝒢|(nk)(nsk)us1u(nskk1).𝒢binomial𝑛𝑘binomial𝑛𝑠𝑘𝑢𝑠1𝑢binomial𝑛𝑠𝑘𝑘1|\mathcal{G}|\leq{n\choose k}-{n-s\choose k}-\frac{u-s-1}{u}{n-s-k\choose k-1}. (39)

Proof of Theorem 22.

We prove the theorem by contradiction. Fix t1𝑡1t\geq 1 and take a family \mathcal{F} with δt()>(ntst)(nstst)subscript𝛿𝑡binomial𝑛𝑡𝑠𝑡binomial𝑛𝑠𝑡𝑠𝑡\delta_{t}(\mathcal{F})>{n-t\choose s-t}-{n-s-t\choose s-t}. It cannot be a subfamily of 𝒜0(n,k,s)subscript𝒜0𝑛𝑘𝑠{\mathcal{A}}_{0}(n,k,s) since δt()>δt(𝒜0(n,k,s))subscript𝛿𝑡subscript𝛿𝑡subscript𝒜0𝑛𝑘𝑠\delta_{t}(\mathcal{F})>\delta_{t}({\mathcal{A}}_{0}(n,k,s)). Therefore, τ()s+1𝜏𝑠1\tau(\mathcal{F})\geq s+1 and, assuming that ν()s𝜈𝑠\nu(\mathcal{F})\leq s, we conclude that |||\mathcal{F}| satisfies (39). By simple double counting, we have

δt()(kt)(nt)[(nk)(nsk)us1u(nskk1)].subscript𝛿𝑡binomial𝑘𝑡binomial𝑛𝑡delimited-[]binomial𝑛𝑘binomial𝑛𝑠𝑘𝑢𝑠1𝑢binomial𝑛𝑠𝑘𝑘1\delta_{t}(\mathcal{F})\leq\frac{{k\choose t}}{{n\choose t}}\Big{[}{n\choose k}-{n-s\choose k}-\frac{u-s-1}{u}{n-s-k\choose k-1}\Big{]}.

Note that (nstkt)=(kt)(nst)(nsk)binomial𝑛𝑠𝑡𝑘𝑡binomial𝑘𝑡binomial𝑛𝑠𝑡binomial𝑛𝑠𝑘{n-s-t\choose k-t}=\frac{{k\choose t}}{{n-s\choose t}}{n-s\choose k} and (ntkt)=(kt)(nt)(nk)binomial𝑛𝑡𝑘𝑡binomial𝑘𝑡binomial𝑛𝑡binomial𝑛𝑘{n-t\choose k-t}=\frac{{k\choose t}}{{n\choose t}}{n\choose k}. We have

δt(𝒜0(n,k,s))δt()(kt)(us1)(nt)u(nskk1)[(kt)(nst)(kt)(nt)](nsk)=subscript𝛿𝑡subscript𝒜0𝑛𝑘𝑠subscript𝛿𝑡binomial𝑘𝑡𝑢𝑠1binomial𝑛𝑡𝑢binomial𝑛𝑠𝑘𝑘1delimited-[]binomial𝑘𝑡binomial𝑛𝑠𝑡binomial𝑘𝑡binomial𝑛𝑡binomial𝑛𝑠𝑘absent\delta_{t}({\mathcal{A}}_{0}(n,k,s))-\delta_{t}(\mathcal{F})\geq\frac{{k\choose t}(u-s-1)}{{n\choose t}u}{n-s-k\choose k-1}-\Big{[}\frac{{k\choose t}}{{n-s\choose t}}-\frac{{k\choose t}}{{n\choose t}}\Big{]}{n-s\choose k}=
(kt)(nt)[us1u(nskk1)[i=0t1ninsi1](nsk)]=().binomial𝑘𝑡binomial𝑛𝑡delimited-[]𝑢𝑠1𝑢binomial𝑛𝑠𝑘𝑘1delimited-[]superscriptsubscriptproduct𝑖0𝑡1𝑛𝑖𝑛𝑠𝑖1binomial𝑛𝑠𝑘\frac{{k\choose t}}{{n\choose t}}\Bigg{[}\frac{u-s-1}{u}{n-s-k\choose k-1}-\Big{[}\prod_{i=0}^{t-1}\frac{n-i}{n-s-i}-1\Big{]}{n-s\choose k}\Bigg{]}=(*).

We have i=0t1ninsi1(1+snst)t1.superscriptsubscriptproduct𝑖0𝑡1𝑛𝑖𝑛𝑠𝑖1superscript1𝑠𝑛𝑠𝑡𝑡1\prod_{i=0}^{t-1}\frac{n-i}{n-s-i}-1\leq(1+\frac{s}{n-s-t})^{t}-1. It is not difficult to verify that for θ<12m𝜃12𝑚\theta<\frac{1}{2m} one has (1+θ)m1+2mθsuperscript1𝜃𝑚12𝑚𝜃(1+\theta)^{m}\leq 1+2m\theta. Therefore, assuming that

ns+t+2st,𝑛𝑠𝑡2𝑠𝑡n\geq s+t+2st, (40)

we have

i=0t1ninsi12tsnst.superscriptsubscriptproduct𝑖0𝑡1𝑛𝑖𝑛𝑠𝑖12𝑡𝑠𝑛𝑠𝑡\prod_{i=0}^{t-1}\frac{n-i}{n-s-i}-1\leq\frac{2ts}{n-s-t}. (41)

On the other hand, we have (1θ)m1mθsuperscript1𝜃𝑚1𝑚𝜃(1-\theta)^{m}\geq 1-m\theta and tk1𝑡𝑘1t\leq k-1, and

(nskk1)(nsk)=knsk+1i=0k1nski+1nsi>knst(1k1nsk)k>binomial𝑛𝑠𝑘𝑘1binomial𝑛𝑠𝑘𝑘𝑛𝑠𝑘1superscriptsubscriptproduct𝑖0𝑘1𝑛𝑠𝑘𝑖1𝑛𝑠𝑖𝑘𝑛𝑠𝑡superscript1𝑘1𝑛𝑠𝑘𝑘absent\frac{{n-s-k\choose k-1}}{{n-s\choose k}}=\frac{k}{n-s-k+1}\prod_{i=0}^{k-1}\frac{n-s-k-i+1}{n-s-i}>\frac{k}{n-s-t}\Big{(}1-\frac{k-1}{n-s-k}\Big{)}^{k}>
knst(1(k1)knsk)>k2(nst),𝑘𝑛𝑠𝑡1𝑘1𝑘𝑛𝑠𝑘𝑘2𝑛𝑠𝑡\frac{k}{n-s-t}\Big{(}1-\frac{(k-1)k}{n-s-k}\Big{)}>\frac{k}{2(n-s-t)},

provided

ns+k+2k(k1).𝑛𝑠𝑘2𝑘𝑘1n\geq s+k+2k(k-1). (42)

We conclude that, provided that (40) and (42) hold, we get

()>(kt)(nt)[us1uk2(nst)2tsnst](nsk),binomial𝑘𝑡binomial𝑛𝑡delimited-[]𝑢𝑠1𝑢𝑘2𝑛𝑠𝑡2𝑡𝑠𝑛𝑠𝑡binomial𝑛𝑠𝑘(*)>\frac{{k\choose t}}{{n\choose t}}\Bigg{[}\frac{u-s-1}{u}\frac{k}{2(n-s-t)}-\frac{2ts}{n-s-t}\Bigg{]}{n-s\choose k},

which is nonnegative provided k4tsuus1𝑘4𝑡𝑠𝑢𝑢𝑠1k\geq 4ts\frac{u}{u-s-1}. This inequality holds for k5ts𝑘5𝑡𝑠k\geq 5ts and u9s𝑢9𝑠u\geq 9s. The last inequality is satisfied for n2k2𝑛2superscript𝑘2n\geq 2k^{2}, since then n2k2(9s+s)k(9s+s1)(k1)+s+k𝑛2superscript𝑘29𝑠𝑠𝑘9𝑠𝑠1𝑘1𝑠𝑘n\geq 2k^{2}\geq(9s+s)k\geq(9s+s-1)(k-1)+s+k. We note that with this choice of n𝑛n and k𝑘k both (40) and (42) hold.

For t=1𝑡1t=1 one may improve (41) to nns1sns𝑛𝑛𝑠1𝑠𝑛𝑠\frac{n}{n-s}-1\leq\frac{s}{n-s} and the condition on k𝑘k may be relaxed to k3s𝑘3𝑠k\geq 3s. The equality part of the statement follows easily from the fact that strict inequality is obtained in the case when τ()s+1𝜏𝑠1\tau(\mathcal{F})\geq s+1. ∎

7 Conclusion

In this paper we explored several question concerning intersecting families. Some of these questions remain only partially resolved, and it would be highly desirable to settle them.

First of all, it would be desirable to understand the structure of families with diversity larger than (n3k2)binomial𝑛3𝑘2{n-3\choose k-2}. As shown in [23], no such family exist for n>Ck𝑛𝐶𝑘n>Ck with some absolute constant C𝐶C. It is believed to be true for n>3k2𝑛3𝑘2n>3k-2. For 2k<n<3k2𝑘𝑛3𝑘2k<n<3k, however, we do have such families, and both the proof of the conjecture above and the understanding of their structure is interesting on its own and would be helpful in different questions (for more information, see [23]).

In this paper we have applied the machinery of Section 3, based on papers [9], [24], to the setting of general families (see Theorem 16). This gave a reasonable classification of all large intersecting families. However, it is by no means complete.

Problem 1.

To what extent one could relax the condition on diversity and/or on t𝑡t in Theorem 16?

Problem 2.

In terms of Theorem 16, is there a reasonable way to compare the sizes of intersecting families generated by typical minimal families? In particular, we believe that, if (1¯)¯1\mathcal{F}(\bar{1}) contains a typical minimal subfamily 𝒢𝒢\mathcal{G}, such that |F𝒢F|=t5subscript𝐹𝒢𝐹𝑡5|\cap_{F\in\mathcal{G}}F|=t\geq 5, then

|||𝒥kt+1|subscript𝒥𝑘𝑡1|\mathcal{F}|\leq|\mathcal{J}_{k-t+1}| (43)

with equality only possible if \mathcal{F} is isomorphic to 𝒥ssubscript𝒥𝑠\mathcal{J}_{s}.

We believe that Theorem 16 is an important step towards classification of families with large covering numbers τ()𝜏\tau(\mathcal{F}) (the size of the smallest subset that intersects any set from \mathcal{F}). An important result in this direction we obtained by Frankl [4], who resolved this problem for τ()=3𝜏3\tau(\mathcal{F})=3 and, again, for large enough n=n(k)𝑛𝑛𝑘n=n(k).

Problem 3.

Extend Theorem 16 to families with τ()k𝜏𝑘\tau(\mathcal{F})\geq k.

The next question concerns the degree version of the Hilton-Minler theorem.

Problem 4.

Is there an example for n=2k+1𝑛2𝑘1n=2k+1 (n=2k+ct𝑛2𝑘𝑐𝑡n=2k+ct, c𝑐c is a small constant), such that there exists a non-trivial intersecting family \mathcal{F} with minimal 111-degree (t𝑡t-degree) higher than that of the Hilton-Milner family?

One reason to believe that the answer to this question is positive is that the degrees of elements in the Hilton-Milner family are irregular, even if we exclude the element of the highest degree out of consideration.

Finally, the following question concerning cross-intersecting families seem interesting for us.

Problem 5.

Consider two cross-intersecting families 𝒜,([n]k)𝒜binomialdelimited-[]𝑛𝑘{\mathcal{A}},\ {\mathcal{B}}\subset{[n]\choose k} that are disjoint. Is it true that

min{|𝒜|,||}12(n1k1)?𝒜12binomial𝑛1𝑘1?\min\{|{\mathcal{A}}|,|{\mathcal{B}}|\}\leq\frac{1}{2}{n-1\choose k-1}?

References

  • [1] B. Bollobás, D.E. Daykin, P. Erdős, Sets of independent edges of a hypergraph, Quart. J. Math. Oxford Ser. 27 (1976), N2, 25–32.
  • [2] P. Erdős, A problem on independent r-tuples, Ann. Univ. Sci. Budapest. 8 (1965) 93–95.
  • [3] P. Erdős, C. Ko, R. Rado, Intersection theorems for systems of finite sets, The Quarterly Journal of Mathematics, 12 (1961) N1, 313–320.
  • [4] P. Frankl, On intersecting families of finite sets, Bull. Austral. Math. Soc. 21 (1980), 363– 372.
  • [5] P. Frankl, Erdos-Ko-Rado theorem with conditions on the maximal degree, Journal of Combinatorial Theory, Series A 46 (1987), N2, 252–263.
  • [6] P. Frankl, Improved bounds for Erdős’ Matching Conjecture, Journ. of Comb. Theory Ser. A 120 (2013), 1068–1072.
  • [7] P. Frankl, On the maximum number of edges in a hypergraph with given matching number, Discrete Applied Mathematics 216 (2017), 562–581.
  • [8] P. Frankl, J. Han, H. Huang, Y. Zhao A degree version of Hilton-Milner theorem, arXiv:1703.03896v2
  • [9] P. Frankl, A. Kupavskii, Erdős-Ko-Rado theorem for {0,±1}0plus-or-minus1\{0,\pm 1\}-vectors, arXiv:1510.03912
  • [10] P. Frankl, A. Kupavskii, Families with no s𝑠s pairwise disjoint sets, Journal of London Mathematical Society (2017), arXiv:1607.06122
  • [11] P. Frankl, A. Kupavskii, Two problems of P. Erdős on matchings in set families, submitted, arXiv:1607.06126
  • [12] P. Frankl, N. Tokushige, Some best possible inequalities concerning cross-intersecting families, Journal of Combinatorial Theory, Series A 61 (1992), N1, 87–97.
  • [13] P. Frankl, N. Tokushige, A note on Huang–Zhao theorem on intersecting families with large minimum degree, Discrete Mathematics 340 (2016), N5, 1098–1103.
  • [14] J. Han, Y. Kohayakawa, The maximum size of a non-trivial intersecting uniform family that is not a subfamily of the Hilton–Milner family, Proc. Amer. Math. Soc. 145 (2017) N1, 73–87.
  • [15] H. Hán, Y. Person, M. Schacht, On perfect matchings in uniform hypergraphs with large minimum vertex degree, SIAM Journal on Discrete Mathematics 23 (2009), N2, 732–748.
  • [16] A.J.W. Hilton, E.C. Milner, Some intersection theorems for systems of finite sets, Quart. J. Math. Oxford 18 (1967), 369–384.
  • [17] H. Huang and Y. Zhao, Degree versions of the Erdős-Ko-Rado theorem and Erdős hypergraph matching conjecture, J. Combin. Theory Ser. A, to appear
  • [18] F. Ihringer, A. Kupavskii, Regular intersecting families, preprint.
  • [19] G. Katona, A theorem of finite sets, “Theory of Graphs, Proc. Coll. Tihany, 1966”, Akad, Kiado, Budapest, 1968; Classic Papers in Combinatorics (1987), 381-401.
  • [20] A. Kostochka, Dhruv Mubayi, The structure of large intersecting families Proc. Amer. Math. Soc. 145 (2017), N6, 2311–2321.
  • [21] J.B. Kruskal, The Number of Simplices in a Complex, Mathematical optimization techniques 251 (1963), 251-278.
  • [22] D. Kühn, D. Osthus, Embedding large subgraphs into dense graphs, Surveys in combinatorics (2009). Papers from the 22nd British combinatorial conference, St. Andrews, UK, July 5–10, 2009, pages 137–167.
  • [23] A. Kupavskii, Diversity of intersecting families, submitted
  • [24] A. Kupavskii, D. Zakharov, Regular bipartite graphs and intersecting families, arXiv:1611.03129